(C++) - 백준(BOJ) 11068 : 회문인 수

https://www.acmicpc.net/problem/11068

11068번: 회문인 수

모든 경우의 수를 확인하는 brute force문제였습니다.

📕 풀이방법

📔 입력 및 초기화

test case t, 10진수 num을 선언 후 매 t마다 num에 입력받습니다.

📔 풀이과정

정답을 출력할 지역변수 isValid를 선언 후 0으로 초기화합니다.

b진법의 범위가 2 ~ 64이므로 for loop를 해당 범위만큼 수행합니다.

1. b진법으로 표현된 vector를 반환하는 getNotation함수를 수행합니다. 거꾸로 반환이 되지만 회문인지만 검사하면 되므로 상관이 없습니다. 반환된 vector를 notationB라는 지역변수를 선언해 저장합니다.

2. palindrome(회문)인지 검사하는 함수 isPalindrome을 수행해 vector의 양 옆 원소가 같은지 검사합니다.

3. b진법으로 표현된 수가 한 번이라도 회문이 될 수 있다면 isValid를 1로 만들고 break해줍니다.

📔 정답출력

isValid를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;

vector <int> getNotation(int num, int b){
    int tmp = num;
    vector <int> notationB;
    while(tmp){
        notationB.push_back(tmp % b);
        tmp /= b;
    }
    return notationB;
}

bool canMakePalindrome(vector <int> notationB){
    int sz = notationB.size();
    for(int i = 0; i < sz / 2; i++)
        if(notationB[i] != notationB[sz - i - 1]) 
            return false;
    return true;
}

int main(){
    int t, num;
    cin >> t;
    while(t--){
        cin >> num;
        int isValid = 0;
        for(int b = 2; b <= 64; b++){
            vector <int> notationB = getNotation(num, b);
            if(canMakePalindrome(notationB)) { isValid = 1; break; }
        }
        cout << isValid << '\n';
    }
}