백준 3944번 Python / 수학

문제풀이 GitHub

https://github.com/Seokii/baekjoon

GitHub - Seokii/baekjoon: Daily Commit for Baekjoon

문제링크

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

3944번: 나머지 계산

 

풀이1 (시간 초과)

t = int(input())

for _ in range(t):
    b,d = input().split()
    b = int(b)
    print(int(d, b) % (b - 1))

int() 형 변환을 통해 다양한 진수를 10진수로 처리하는 방법의 풀이입니다.

예를 들어, int("12345678", 7)이라면 7진수 12345678을 10진수 형태로 바꿀 수 있습니다.

10진수로 변환 후, b-1로 나눈 나머지를 출력합니다.

 이 풀이로 푸니 시간 초과가 발생했습니다.

 

풀이2 (시간 초과)

t = int(input())

for _ in range(t):
    b,d = input().split()
    b = int(b)
    tmp = 0
    
    # print(int(d, b) % (b - 1))

    for i in range(len(d)):
        tmp += int(d[i])

    print(tmp % (b-1))

10진수 12345의 수를 예로 들겠습니다.

12345는 10000 * 1 + 1000 * 2 + 100 * 3 + 10 * 4 + 1 * 5의 형태로 나타낼 수 있습니다.

이 수를 다시 나타내면,

(9999*1 + 1*1) + (999*2 + 1*2) + (99*3 + 1*3) + (9*4 + 1*4) + (1*5) 입니다.

문제에서의 b-1의 꼴로 나눈다고 가정한다면 위의 형태에서

1*1, 1*2, 1*3, 1*4, 1*5만 남게 됩니다.

결론적으로, 모든 자리의 숫자를 더해준 후 그 값을 b-1의 값으로 나눈 나머지가 전체 계산 과정의 나머지와 같다는 의미를 가집니다.

 

그래서, 각 자리의 수를 for 문으로 더한 후 그 값으로 나머지를 구했더니 역시나 시간 초과가 발생했습니다.

 

풀이3 (정답)

t = int(input())

for _ in range(t):
    b,d = input().split()
    b = int(b)
    tmp = 0
    # print(int(d, b) % (b - 1))

    """
    for i in range(len(d)):
        tmp += int(d[i])
    """

    tmp = sum(map(int, list(d)))
    print(tmp % (b-1))

풀이2와 과정은 똑같습니다.

for문 대신 sum() 함수를 사용해 각 자리의 수를 더했습니다.

그 결과, 시간 초과가 발생하지 않고 정답 처리되었습니다.