Python으로 진수 변환 후 자릿수 합 구하기: k진수 자릿수 합 계산 프로그램

이 글에서는 10진수로 주어진 숫자 n을 k진수로 변환한 뒤, 변환된 수의 각 자릿수를 모두 더한 값을 구하는 방법을 다룹니다. 자릿수 합을 계산할 때는 각 자릿수를 10진수 값으로 취급한다는 점에 유의해야 합니다.

문제 예시

예를 들어 n = 985, k = 8이 입력으로 주어진 경우를 생각해 보겠습니다. 985를 8진수로 변환하면 1731이 되고, 따라서 자릿수 합은 1 + 7 + 3 + 1 = 12가 됩니다.

풀이 접근 방식

이 문제는 진법 변환 과정에서 나오는 나머지들을 활용하면 간단하게 해결할 수 있습니다. 알고리즘은 다음과 같습니다.

• 결괏값을 저장할 변수 ans를 0으로 초기화합니다.
• n이 k보다 크거나 같은 동안 반복합니다.
• 각 반복마다 n을 k로 나눈 나머지(n mod k)를 ans에 더합니다.
• n을 n을 k로 나눈 몫(n // k)으로 갱신합니다.
• 반복이 끝나면 마지막으로 남은 n(최상위 자릿수)을 ans에 더합니다.
• ans를 반환합니다.

이 방식은 실제 손으로 진법을 변환할 때와 동일한 원리입니다. 나눗셈의 나머지가 낮은 자리부터 차례대로 만들어지기 때문에, 그 나머지들을 모두 더하면 곧 자릿수 합이 됩니다.

Python 구현 코드

def solve(n, k):
    ans = 0
    while n >= k:
        ans = ans + n % k
        n = n // k
    ans = ans + n
    return ans

n = 985
k = 8
print(solve(n, k))

입력

n = 985, k = 8

출력

12

코드 설명

n % k는 현재 n을 k진수로 표현했을 때 가장 낮은 자릿수를 의미하고, n // k는 그 자릿수를 제거한 나머지 부분을 의미합니다. 이 과정을 n이 k보다 작아질 때까지 반복하면 모든 자릿수를 한 번씩 더하게 되며, 마지막으로 남은 n이 최상위 자릿수이므로 반복 종료 후 한 번 더 더해줍니다.

시간 복잡도는 n을 k로 계속 나누므로 O(log_k n)이며, 공간 복잡도는 O(1)로 매우 효율적입니다.