[백준] 1437 - 수 분해

 

문제 : 1437 - 수 분해

바로가기

 

문제 설명

음이 아닌 정수 N을 한 개 이상의 음이 아닌 정수의 합으로 나타낼 때, 이를 "N을 분해한다"라고 부르자.

 

예를 들어, 4 = 1+1+1+1 = 1+1+2 = 1+3 = 2+2 = 4 로 나눌 수 있다.

 

분해 곱이란 N을 분해해서 나타난 수들을 전부 곱한 것을 의미한다. N=4일 때, 분해 곱은 다음과 같다.

• 4 = 1+1+1+1, 곱 : 1×1×1×1 = 1
• 4 = 1+1+2, 곱 : 1×1×2 = 2
• 4 = 1+3, 곱 : 1×3 = 3
• 4 = 2+2, 곱 : 2×2 = 4
• 4 = 4, 곱 : 4

N이 주어졌을 때, 그 수의 분해 곱의 최댓값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 음이 아닌 정수 N이 주어진다. N은 1,000,000보다 작거나 같다.

 

출력

첫째 줄에 입력으로 주어진 수의 분해 곱의 최댓값을 10,007로 나눈 나머지를 출력한다.

 

예제

입력	출력
7	12
0	0
1	1
5	6
9931	4664

 

해답 및 해설

수학적 해석

 분해곱을 구할 때, 분해해서 나타난 수들 중 서로 다른 수 a와 b가 있다 해보자. 이 때 원래 두 수를 곱한 값 ab보다 두 수를 평균한 뒤 곱한 값 ((a+b)/2)^2가 더 크다. (산술 평균 기하 평균 대소비교) 따라서 분해곱의 최댓값을 생각할 때는 모든 수가 같은 수로 분해되어져 있는 경우를 생각하는게 좋다.

 

자연수 N을 a라는 숫자로 똑같이 분해해서 곱했다고 가정해보자. 그러면 분해곱의 결과는 a^(N/a)일 것이다. 이 때 해당 값이 최대가 되는 a를 구해주면 된다. a에 대해서 미분해주면 다음과 같이 된다.

이 때 a의 거듭제곱 부분은 항상 양수이기 때문에, log(a) -1 이 0이 되어야 미분값이 0이 됨을 알 수 있다. 이 때 a의 값은 자연상수 e이다.

 

따라서 분해곱은 e와 가장 가까운 3으로 나눌 때가 가장 크다. 나머지가 1인 경우는 3과 1로 쪼개지 말고 4로 만드는게 좋다. 결국 답은 3의 거듭제곱 형태에 나머지가 1일 때는 4, 나머지가 2일 때는 2가 곱해진 수가 될 것이다.

 

파이썬 (Python)

def solution(n):
    if n in (0, 1):
        return n
    
    q = n//3
    r = n%3
    answer = 1
    
    if r == 1:
        r = 4
        q -= 1
    elif r == 0:
        r = 1
    
    answer = 3**q * r
    
    if answer > 10007:
        answer %= 10007
    
    return answer

n = int(input())
print(solution(n))

길게 쓰면 다음과 같다.

 

n=int(input())
print((3**(n//3-1)*(3,4,6)[n%3]%10007,n)[n<3])

짧게 이렇게 줄여 쓸 수도 있었다. 신기하다.