[백준] 1437번: 수 분해 풀이 (수학적 증명 포함)

사용한 기술 스택들:  

 

1437번: 수 분해 (acmicpc.net)

1437번: 수 분해

이 문제는 수를 1개 이상의 정수로 분해해서 그 분해한 수들의 곱의 최댓값을 구하는 문제이다. 수학적인 증명이 인터넷에 한국어로 없길래 블로그를 써본다.

 

증명의 대한 아이디어는 여기서 얻었다.

Breaking an Integer to get Maximum Product - GeeksforGeeks

Breaking an Integer to get Maximum Product - GeeksforGeeks

 

코드:

import sys

input = lambda: sys.stdin.readline().rstrip()
n = int(input())
m=10007
if n<5:
    print(n)
elif n%3==0:
    print(pow(3,n//3,m))
elif n%3==1:
    print((pow(3,(n-4)//3,m)*4)%m)
else:
    print((pow(3,(n-2)//3,m)*2)%m)

 

 

풀이:

 

자세히 패턴을 살펴보면 5 이상의 숫자들은 최대곱이 2와 3의 곱으로만 이루어져 있다는 것을 알 수 있다. 어떻게 이게 최댓값인지는 수학적으로 증명이 가능하다.

 

먼저 $n$이라는 숫자를 똑같은 $x$라는 숫자로 나누어보자.

 

그렇다면 수는 $\frac{n}{x}$개로 나누어지고 이 숫자의 곱은 $x^{\frac{n}{x}}$이 될 것이다.

 

그렇다면 이 곱의 최댓값을 찾으려 한다면 미분을 해주어서 이 미분 값이 0이 되는 $x$가 답이 될 것이다.

 

미분을 하면 $$ nx^{\frac{n}{x}-2}\left(1-\ln\left(x\right)\right) $$이라는 답이 나오게 되고 $x\neq0$ 이기 때문에 $x$는 $e$라는 값에서 최댓값이 나오게 된다.

 

$e=2.718281828...$ 인 값이기 때문에 정수에서의 최댓값을 찾으려면 2나 3 같은 $e$에서 최대한 가까운 값을 사용하면 된다. 여기서 사람들은 2를 처음에 최대한 사용하여 곱을 만드려 하지만 $e$는 3과 더 가깝기 때문에 최대한 3을 사용하는 게 좋다.

 

그래서 코드의 로직을 보자면,

 

1. 4 이하일 때는 어차피 자기 자신이 제일 큰 곱이다
2. 3으로 나누어 떨어지면 $n$은 3의 곱으로 이루어진 $3^{\frac{n}{3}}$이 제일 크다
3. 3으로 나눠서 1이 남으면 마지막 곱을 $3\times 1$이나 $2\times2$로 할 수 있는데 여기서는 $e$와의 거리의 합이 3과 1이 2만큼 떨어져 있고 2와 2는 1.4 정도 떨어져 있기 때문에 $2\times2=4$를 곱하는 게 더 큰 값을 얻을 수 있다
4. 마지막으로 3으로 나눠서 2가 남으면 당연히 $e$와의 거리의 합이 1과 1보단(총 3.4 거리) 2가(총 0.7 거리) 더 가깝기 때문에 2를 곱해준다.

 

파이썬의 pow함수를 사용하면 나머지를 구하는 거듭제곱을 할 때 시간 복잡도가 $O(log(N))$ 이기 때문에 사용해준다.

 

마지막 코드에서 % m을 하는 이유는 모듈러 법칙에 의해서 $(A\times B)  \bmod{M}=((A \bmod{M})\times (B \bmod{M}))mod{M}$ 이기 때문에 나머지가 뒤에 2나 4처럼 곱해진 수 때문에 10007을 넘어가는 걸 방지하기 위해서 한번 더 모듈러 연산을 한다.

 

소스코드:

baekjoonProblems/수_분해.py at main · LimePencil/baekjoonProblems (github.com)

GitHub - LimePencil/baekjoonProblems: 백준 코딩문제 자바&파이썬 해답