[백준] 21275번 폰 호석만

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

21275번: 폰 호석만

 

문제

폰 호석만은 진법 변환의 달인이다. 어떤 진법의 수가 주어져도 모든 다른 진법으로의 변환이 가능한 폰 호석만은 새로운 문제를 내기로 했다. 폰 호석만이 내는 문제는 다음과 같이 진행된다.

먼저 폰 호석만은 수 3개 X, A, B를 결정한다(0 ≤ X < 263, 2 ≤ A ≤ 36, 2 ≤ B ≤ 36, A ≠ B). 이 때 X는 10진법이다. 그 다음에 X를 A진법으로 표현한 수와 B진법으로 표현한 수를 종이에 써 놓는다.

그 다음에 종이에 써져 있는 두 개의 수를 여러분에게 보여주게 된다. 주어진 두 개의 수를 통해 원래 숫자인 X, A, B를 계산해주자. 만약 조건을 만족하는 (X, A, B)로 가능한 조합이 여러 개라면 "Multiple"을 출력하고, 가능한 조합이 없다면 "Impossible"를 출력한다.

 

입력

첫번째 줄에 X를 A진법으로 표현한 값과 X를 B진법으로 표현한 값이 공백으로 구분되어 주어진다. 각 자리수는 0 이상 z 이하이다. a부터 z 는 10부터 35 를 의미한다.

단, 0을 제외한 각 수는 0 으로 시작하지 않으며, 길이는 최대 70 이다.

 

출력

만약 문제의 조건에 맞는 X, A, B가 유일하게 존재한다면, X를 십진법으로 표현한 수와 A와 B를 공백으로 나누어 출력하라. 만약 만족하는 경우가 2가지 이상이라면 "Multiple"을, 없다면 "Impossible"을 출력하라.

 

제한

• 0 ≤ X < 263
• 2 ≤ A ≤ 36
• 2 ≤ B ≤ 36
• A ≠ B
• X는 0 혹은 양의 정수, A와 B는 양의 정수이다.

 

 

풀이

 

numbers = dict()
count = 0
answer = [0, 0]
# 1부터 저장
for i in range(0, 10):
    numbers[str(i)] = i

# a부터 저장
for i in range(26):
    numbers[chr(97+i)] = i+10

dictionary를 이용하여 각 문자가 나타내는 value를 저장하였다. 1:1 2:2 ... A:10 B:11 ... Z:35

a_max = max(list(a))
b_max = max(list(b))

a와 b에서 가장 큰 문자를 찾아서 a_max와 b_max로 저장하였다.
a의 최대값이 A라고 가정할 때 1~10진수로 변환하는 경우에는 A를 처리할 수 없기 때문에 문제가 발생한다.
즉 a, b의 최대보다 큰 진수로만 변환을 해야 문제없이 모든 숫자를 변환할 수 있는 것이다.

 

def trans_notation(string, notation):
    temp = 0
    for i in range(len(string)):
        temp += ((int(notation)**i) * numbers[string[-1-i]])
    return temp

진수 변환을 위해서 trans_notation함수를 구현하였다.
인자로는 문자열과 진수를 받아서 해당 숫자를 진수의 자릿수로 곱한 값을 반환하였다.
string[-1-i]는 맨 끝 글자부터 1칸씩 앞으로 오는 것으로 숫자로 따지면 12345에서 5 -> 1로 계산하는 것이다.

 

for i in range(numbers[a_max]+1, 37):
    for j in range(numbers[b_max]+1, 37):
        if i == j:
            continue
        if trans_notation(a, i) == trans_notation(b, j):
            if trans_notation(a, i) >= 2**63:
                continue
            answer[0] = i
            answer[1] = j
            count += 1

아까 계산한 a_max와 b_max 보다 큰 진수들로 변환하면서 두 숫자가 같아지는 경우에는  count를 1 증가시켰다.
A와 B 진법은 동일하지 않기 때문에 i == j 인 경우에는 체크하지 않고 continue를 이용하여 넘어간다.

답이 단 1개만 있는 경우에는 몇 진수인지 출력하기 위해서 answer에 해당 값을 넣어줬다.

 

if count == 0:
    print("Impossible")
elif count > 1:
    print("Multiple")
elif count == 1:
    print(trans_notation(a, answer[0]), answer[0], answer[1])

count를 체크해서 답을 출력하면 된다.

 

 

전체 코드

a,b=map(str,input().split())

numbers = dict()
count = 0
answer = [0, 0]
# 1부터 저장
for i in range(0, 10):
    numbers[str(i)] = i

# a부터 저장
for i in range(26):
    numbers[chr(97+i)] = i+10

a_max = max(list(a))
b_max = max(list(b))

def trans_notation(string, notation):
    temp = 0
    for i in range(len(string)):
        temp += ((int(notation)**i) * numbers[string[-1-i]])
    return temp

for i in range(numbers[a_max]+1, 37):
    for j in range(numbers[b_max]+1, 37):
        if i == j:
            continue
        if trans_notation(a, i) == trans_notation(b, j):
            if trans_notation(a, i) >= 2**63:
                continue
            answer[0] = i
            answer[1] = j
            count += 1

if count == 0:
    print("Impossible")
elif count > 1:
    print("Multiple")
elif count == 1:
    print(trans_notation(a, answer[0]), answer[0], answer[1])

이 문제의 경우에는 다른 언어는 2^63이라는 값 때문에 타입을 생각해야해서 어렵지만 파이썬은 따로 타입을 
지정하지 않기 때문에 알고리즘만 구현하면 풀린다고 들었다.