BOJ 4328 - 기초 나머지 계산

문제

b진법 수 P를 b진법 수 M으로 나눈 나머지를 b진법으로 출력하라.

입력

여러 줄에 걸쳐 b, P, M이 주어지며, b가 0이면 종료한다.

출력

각 케이스마다 P mod M을 b진법으로 출력한다.

예제

입력	출력
`10 1234 100` `0`	`34`

풀이

b진법 수를 10진법으로 변환하여 나머지를 구한 뒤 다시 b진법으로 변환한다.

P와 M을 b진법 문자열로 읽어 int(str, b)로 10진수 변환한다
10진수에서 나머지 연산을 수행한다
결과를 다시 b진법으로 변환하여 출력한다

핵심 아이디어: Python의 int(string, base) 함수로 임의 진법 문자열을 정수로 변환하고, 반복 나눗셈으로 다시 b진법으로 변환한다.

코드

while 1:
    li = list(map(int, input().split()))
    if li[0] == 0:
        break
    b, p, m = li[0], li[1], li[2]
    n = int(str(p), b) % int(str(m), b)
    res = []
    while n >= b:
        res.append(str(n % b))
        n = n // b
    res.append(str(n))
    print(int("".join(res[::-1])))

복잡도

시간: O(len(P) + len(M))
공간: O(len(result))

문제