[Python] 1437번 수 분해

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

1437번: 수 분해

---

 

22/09/27

 

 

증명하기에는 살짝 어려웠던 문제로, 기발한 아이디어가 돋보였던 문제이다.

---

 

문제 접근 방식:

 

 

이 문제를 처음 풀 때에 직관적으로 최대한 많은 수들로 나눠야 한다고 생각했다.

 

직관적으로 생각했을 때에도, 어떤 큰 숫자가 있으면 그 숫자를 작은 수 10개로 나눠서 곱하는 것과 큰 수 2개로 나누어서 곱하는 것을 비교했을 때, 당연히 전자가 더 크다고 생각했기 때문이다.

 

예를 들자면, 10을 2 + 2 + 2 + 2 + 2로 나누는 것과 5 + 5로 나누는 것을 비교했을 때, 2^5 > 5^2이다.

 

하지만 이것만으로는 부족했다. 나누는 것도 너무 많이 나누면, 손해라고 생각했기 때문이다,

 

예를 들자면 5를 1 + 1 + 1 + 1 + 1로 분해하면 1은 곱해도 1이기 때문에 2 + 3으로 나눈 것보다 작게 나온다.

 

그래서 이에 영감을 받아 첫번째 사실을 증명했다.

1. 기존의 수를 분해할 때 1이 나오도록 분해하는 것은 손해이다.

증명) 어떤 수 N을 A + B로 분해한다고 가정하자.
그리고 또 다른 분해 방법으로, (A - 1) + B + 1로 분해한다고 가정하자.
(이때, 일반성을 잃지 않고, A > B > 0이라고 가정해도 된다.)
우리는 AB > (A - 1)B = AB - B라는 사실을 알고 있기 때문에, 1이 나오도록 분해하는 것은 손해이다.

나는 두 번째로, 최대한 숫자들을 분해할 때, 숫자들의 차이가 제각각이 되면 안 된다고 생각했다.

 

예를 들어, 10을 쪼갤 때 2 + 8로 쪼개는 것과 3 + 7로 쪼개는 것을 비교해보면 3 + 7로 쪼개는 것이 숫자가 더 크게 나온다.

 

때문에 이에 영감을 받아 두번째 사실을 증명했다.

2. 기존의 수를 분해할 때, 쪼개진 수들의 차이가 최대한 적도록 분해해야 한다.

증명) 어떤 수 N을 A + B로 분해했다고 가정하자.
그리고 또다른 분해 방법으로, (A - 1) + (B + 1)로 분해했다고 가정하자.
(일반성을 잃지 않고, A > A - 1 > B + 1 > B라고 가정하자)
그러면, 첫번째 분해 방법을 통해 나온 분해 곱은 AB이고, 두 번째 분해 방법을 통해 나온 분해 곱은 AB + A - B - 1이다.
A > B > 0이기 때문에 A - B > 0이고, A - B - 1 > -1이다.
이때, 모두 정수이기 때문에, A - B - 1 >= 0
따라서, AB <= AB + A - B - 1이다.

이 말은 곧, 수를 분해할 때 같은 숫자 여러 개로 분해하는 것이 이득이라는 뜻이다.

 

직관적으로 숫자들의 개수가 많도록 분해하는 것이 이득이라는 사실을 알고 있었고, 1이 나오도록 분해하면 손해라는 사실을 알고 있기 때문에 2나 3, 아니면 4나 5 같은 숫자들로 분해하면 될 것이라고 생각했다.

 

때문에 나는 3으로 분해하는 방법을 택했고, 분해를 계속 하다가 4보다 같거나 작아지는 지점에서 분해를 그만두고 모든 숫자들을 곱했다.(4보다 같거나 작아지는 지점에서 분해를 그만두는 이유는, 4의 최대 분해곱은 4이기 때문이다.)

 

하필이면 2도 아니고 4도 아니고 3이냐...에 관한 엄밀한 증명은 다음 링크를 참고하면 도움이 될 것이다.

 

https://limepencil.tistory.com/15

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

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1437번 수 분해
# 수학, 그리디
N = int(input())
total = 1
if N == 0:
    print(0)
else:
    while True:
        if N <= 4:
            total *= N
            total %= 10007
            break
        N -= 3
        total *= 3
        total %= 10007
    print(total)