[Python] 백준 21275 - 폰 호석만 문제 풀이

Overview

BOJ 21275번 폰 호석만 Python 문제 풀이
분류: Math (수학)

---

문제 페이지

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

---

풀이 코드 - 1

from sys import stdin


# x진수 num을 10진수로 변환
def to_decimal(num: str, x: int) -> int:
    cur, res = 0, 0
    for i in range(len(num)):
        if num[i].isdigit():
            cur = int(num[i])
        else:
            cur = ord(num[i]) - 97 + 10

        # 한 자리의 값이 x진수에서 나올 수 없는 수이면 -1 리턴
        if cur >= x:
            return -1

        res += (x ** (len(num) - i - 1)) * cur
    return res


def main():
    a, b = stdin.readline().split()

    a_decimals, b_decimals = [-1, -1], [-1, -1]
    for i in range(2, 37):
        a_decimals.append(to_decimal(a, i))
        b_decimals.append(to_decimal(b, i))

    res = []
    for i in range(2, 37):
        for j in range(2, 37):
            if i == j:
                continue
            if a_decimals[i] != -1 and a_decimals[i] == b_decimals[j]:
                res.append((a_decimals[i], i, j))

    if len(res) > 1:
        print('Multiple')
    elif not res:
        print('Impossible')
    else:
        print(*res[0], sep=' ')


if __name__ == "__main__":
    main()

a, b를 2진수부터 36진수 까지의 수로 가정했을 때, 10진수로 변환한 값들을 구하여 리스트 a_decimals, b_decimals에 저장한다. 그리고 각 리스트에서 동일한 값을 찾아서 결과를 구한다.

to_decimal(num: str, x: int) 함수는 x진수 num을 10진수로 변환해준다. 만약 x진수에서 나올 수 없는 숫자가 num에 들어있다면 -1을 리턴한다.

---

풀이 코드 - 2

from sys import stdin


# x진수 num을 10진수로 변환
def to_decimal(num: str, x: int, decimals: dict) -> int:
    res = 0
    for i, char in enumerate(num):
        res += (x ** (len(num) - i - 1)) * decimals[char]
    return res


def main():
    a, b = stdin.readline().split()

    decimals = {}
    for i in range(10):
        decimals[str(i)] = i
    for i in range(26):
        decimals[chr(i + 97)] = 10 + i

    a_nums, b_nums = [-1] * 37, [-1] * 37
    a_max, b_max = decimals[max(a)], decimals[max(b)]
    for i in range(a_max + 1, 37):
        a_nums[i] = to_decimal(a, i, decimals)
    for i in range(b_max + 1, 37):
        b_nums[i] = to_decimal(b, i, decimals)

    res = []
    for i in range(a_max + 1, 37):
        for j in range(b_max + 1, 37):
            if i == j:
                continue
            if a_nums[i] == b_nums[j]:
                res.append((a_nums[i], i, j))

    if len(res) > 1:
        print('Multiple')
    elif not res:
        print('Impossible')
    else:
        print(*res[0], sep=' ')


if __name__ == "__main__":
    main()

이전 코드에서 Dict decimals를 추가하고, 탐색 범위를 줄였다.

decimals에는 숫자의 각 자리 문자를 10진수로 변환한 값을 key, value로 저장한다. 그리고 a, b에 들어있는 가장 큰 값을 찾아서, 큰 값을 최소 진수로 정하여 10진수 변환을 진행한다. 10진수 변환 결과는 Lista_nums, b_nums에 저장하고, 각각의 리스트에 동일한 값이 있는지 탐색하여 결과를 구한다.