[백준(BOJ)] 회문인 수(11068번)_C++

아마 대부분 비슷한 문제를 풀어본 적 있었을 것이다.

이 문제의 독특한 점은 2~64진수로 표현했을 때도 회문인지 판단해야 한다는 점이다.

 

B진법으로 변환하는 것은 어렵지 않다.

몫이 0일 때까지 나누면서 나머지를 저장하면 된다.

이 때, 저장되는 값들의 역순이 실제 B진수 값인데 우리는 회문인지 판단만 하면 되므로 굳이 역순으로 바꿀 필요가 없다.

 

B진수를 구했으면 회문인지 판단하면 된다.

이는 그냥 for문으로 대칭되는 각 자리를 비교하면 된다.

 

근데 한 가지 의문이 들 수 있는데 16진수까지는 9보다 큰 수를 A, B, C, ... 으로 표현한다 치더라도 그 이상의 진법에서 뭘로 표현해야할까?

 

그냥 수 자체로 표현하면 된다.

예로 주어진 수가 31이고, 16진수로 변환하고자 한다면

실제 값은 1F 이지만, 우리는 그냥 {1, 15} 형태로 저장하면 된다.

 

 

---

정답 코드

#include <iostream>
#include <vector>

using namespace std;

int T;
vector<int> v;

void dec_to_B(int n, int B){

    while (1){
        
        if (n / B == 0){
            v.push_back(n);
            break;
        }
        
        v.push_back(n % B);
        n /= B;
    }
}

bool Is_palin(){

    for (int i = 0; i < v.size() / 2; i++){

        if (v[i] != v[v.size() - i - 1])
            return false;
    }

    return true;
}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    //input
    cin >> T;

    while (T--){
        int n;
        bool flag = false;

        cin >> n;

        //check palindrom
        for (int B = 2; B <= 64; B++){

            //init
            v.clear();

            dec_to_B(n, B);

            if (Is_palin() == true){
                flag = true;
                break;
            }
        }

        //output
        if (flag == true)
            cout << "1\n";
        else
            cout << "0\n";
    }
}