[백준] 11068 - 회문인 수

🖥️ 시작하며

2진수를 반드는 법을 잘 생각해보면, 2를 나눈 나머지를 저장하고 이를 되돌리는 식임을 알 수 있다. 다른 진법도 똑같다. 여기서는 진수 자체를 구하는 것은 아니고 회문을 구하면 되므로, 순서를 되돌리는 작업은 필요 없다. 해당 아이디어만 떠올리면 쉬운 문제다.

C언어에서 좋은 아이디어만 하나 소개하고자 한다.


while (num) {
    int digit = num % base;
    digits[len++] = digit;
    reversed = reversed * base + digit;
    num /= base;
}

이 코드를 255(10진수)에 적용해 보자:

초기 상태:

num = 255

base = 16

digits = [] (빈 배열)

len = 0

reversed = 0

첫 번째 반복:


digit = 255 % 16 = 15  (16진수로 'F')
digits[0] = 15, len = 1
reversed = 0 * 16 + 15 = 15
num = 255 / 16 = 15

두 번째 반복:


digit = 15 % 16 = 15  (16진수로 'F')
digits[1] = 15, len = 2
reversed = 15 * 16 + 15 = 255
num = 15 / 16 = 0

루프 종료 (num이 0이 되었으므로)

결과:

digits 배열: [15, 15] (16진수로 [F, F])

reversed: 255

len: 2

⚙️ 코드


def is_palindrome(l):
    return l == l[::-1]


def to_base_n(T, base):
    digits = []
    while T:
        digits.append(int(T % base))
        T //= base
    return digits


def Solution(T):
    for base in range(2, 65):
        if is_palindrome(to_base_n(T, base)):
            return 1
    return 0


if __name__ == "__main__":
    import sys

    N = int(sys.stdin.readline())

    for i in range(N):
        T = int(input())
        print(Solution(T))


#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_DIGITS 64 // 64진법

bool is_palindrome(int *arr, int size) {
    for (int i = 0; i < size / 2; i++) {
        if (arr[i] != arr[size - 1 - i]) {
            return false;
        }
    }
    return true;
}

int *to_base_n(long long T, int base, int *size) {
    int *digits = (int *)malloc(MAX_DIGITS * sizeof(int));
    *size = 0;
    while (T) {
        digits[*size] = T % base;
        T /= base;
        (*size)++;
    }
    return digits;
}

int Solution(long long T) {
    for (int base = 2; base <= 64; base++) {
        int size;
        int *digits = to_base_n(T, base, &size);
        if (is_palindrome(digits, size)) {
            free(digits);
            return 1;
        }
        free(digits);
    }
    return 0;
}

int main() {
    int N;
    scanf("%d", &N);

    for (int i = 0; i < N; i++) {
        long long T;
        scanf("%lld", &T);
        printf("%d\n", Solution(T));
    }

    return 0;
}


#include <stdbool.h>
#include <stdio.h>

#define MAX_DIGITS 64

bool is_palindrome_in_base(unsigned long long num, int base) {
    int digits[MAX_DIGITS];
    int len = 0;
    unsigned long long reversed = 0;
    unsigned long long original = num;

    while (num) {
        int digit = num % base;
        digits[len++] = digit;
        reversed = reversed * base + digit;
        num /= base;
    }

    return original == reversed;
}

int solution(unsigned long long T) {
    for (int base = 2; base <= 64; base++) {
        if (is_palindrome_in_base(T, base)) {
            return 1;
        }
    }
    return 0;
}

int main() {
    int N;
    scanf("%d", &N);

    while (N--) {
        unsigned long long T;
        scanf("%llu", &T);
        printf("%d\n", solution(T));
    }

    return 0;
}

[백준] 11068 - 회문인 수

🖥️ 시작하며

⚙️ 코드

📌 소감

댓글