[백준/python3] 11068번: 회문인 수

문제

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

11068번: 회문인 수

---

알고리즘 분류

수학
브루트포스 알고리즘

문제

어떤 수를 왼쪽부터 읽어도, 오른쪽부터 읽어도 같을 때 이 수를 회문인 수라고 한다. 예를 들어, 747은 회문인 수이다. 255도 회문인 수인데, 16진수로 표현하면 FF이기 때문이다. 양의 정수를 입력받았을 때, 이 수가 어떤 B진법 (2 ≤ B ≤ 64)으로 표현하면 회문이 되는 경우가 있는지 알려주는 프로그램을 작성하시오. B진법이란, 한 자리에서 수를 표현할 때 쓸 수 있는 수의 가짓수가 B라는 뜻이다. 예를 들어, 십진법에서 B는 10이다. 

입력

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 64 이상 1,000,000 이하인 하나의 정수로 주어진다.

출력

출력은 표준출력을 사용한다. 하나의 테스트 데이터에 대한 답을 하나의 줄에 출력한다. 각 테스트 데이터에 대해, 주어진 수가 어떤 B진법 (2 ≤ B ≤ 64)으로 표현하여 회문이 될 수 있다면 1을, 그렇지 않다면 0을 출력한다.

예시

---

풀이

여기서 필요한 기능은 2가지이다.

1) 입력 받은 10진수를 B진법으로 변환

- 이를 수행하기 위해 먼저 입력받은 10진수를 divmod()로 몫과 나머지를 튜플로 구한다.
- 이 때 몫이 0이면 나머지를 이용해 미리 작성해둔 T 리스트의 인덱스로 1의 자리수만 반환하면 되지만 그렇지 않은 경우, 한 번 더 변환해 나머지를 찾아 10의 자리수를, 다시 100의 자리수를 구하는 식으로 해야한다. 그러므로 재귀함수를 이용한다.

2) 변환된 수를 회문인지 확인

- 슬라이싱을 통해 수를 뒤집고, 같은지 확인한다.

---

소스코드

def convert(n, b):
    T = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz#$"
    q, r = divmod(n, b)
    if q == 0:
        return T[r]
    else:
        return convert(q, b) + T[r]

def palindrome(s):
    return s==s[::-1]

T = int(input())
for _ in range(T):
    N = int(input())
    flag = 0
    for B in range(2, 65):
        if palindrome(convert(N, B)):
            flag = 1
            break
    print(flag)

이번 주에 출제된 문제들에서 계속 진수 변환과 회문 찾기가 여러 번 반복되어 사용자 정의 함수로 구현하여 보았다.

---