파이썬(Python)으로 숫자의 더 나은 약수를 찾는 프로그램

문제 설명

하나의 숫자 n이 주어졌을 때, 아래 조건에 따라 n의 약수 중에서 '더 나은(better)' 약수를 찾아야 합니다.

두 수 p와 q를 비교할 때, 각 자릿수의 합이 더 큰 수가 더 나은 수로 간주됩니다. 만약 자릿수의 합이 서로 같다면, 실제 값이 더 작은 수가 더 나은 수가 됩니다.

예를 들어 입력이 n = 180이라면 출력은 9가 됩니다. 180의 약수는 [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]이며, 이 중 자릿수의 합이 최대인 수들은 [9, 18, 36, 45, 90, 180]입니다(모두 자릿수의 합이 9). 그중에서도 값이 가장 작은 9가 정답이 됩니다.

해결 접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다.

div := 1, md := 1로 초기화합니다. (div는 정답 약수, md는 지금까지의 최대 자릿수 합)
i를 2부터 n까지 반복합니다.
- k := i
- n mod i > 0이면, 즉 i가 n의 약수가 아니면 다음 반복으로 넘어갑니다.
- s := 0으로 초기화한 뒤, k > 0인 동안 s := s + k mod 10, k := k / 10을 반복하여 i의 자릿수 합을 구합니다.
- s > md이면 md := s, div := i로 갱신합니다.
반복이 끝나면 div를 반환합니다.

예제 코드

아래 파이썬 구현을 통해 더 잘 이해할 수 있습니다.

def solve(n):
    div = 1
    md = 1
    for i in range(2, n + 1):
        k = i
        if n % i > 0:
            continue
        s = 0
        while k > 0:
            s += k % 10
            k //= 10
        if s > md:
            md = s
            div = i

    return div

n = 180
print(solve(n))

참고: 위 코드에서 자릿수를 줄일 때 정수 나눗셈 연산자 //를 사용했습니다. 일반 나눗셈 /를 사용하면 파이썬 3에서 결과가 실수(float)가 되어 무한 루프에 빠질 수 있으므로, 반드시 //를 사용하는 것이 안전합니다.