BOJ 1437 - 수 분해

숫자를 분해한 후 얻을 수 있는 숫자들의 곱을 최대화하는 문제이다.

당연하게도 많은 수를 곱하는것이 이득임은 쉽게 알 수 있다.

그럼 최대한 많은 수를 곱을 최대화하는 것이 관건이 된다.

 

1,2,3은 분해를 하지 않아야 최대이다.

4는 2+2로 분해할 수 있고 이는 최대이다.

5는 2+3으로 분해할 수 있다.

6은 3+3, 7은 3+2+2, 8은 3+3+2로 분해했을 때가 최대이다.

 

이제 알 수 있는 사실은 3을 가능한 많이 포함하는 것이 수를 분해했을 때 최대가 될 수 있는 것이다. 

 

하지만 10과 같은 경우는 3+3+3+1로 나눠진다면 1로 곱하기 때문에 최대로 만들 수 없다.

3을 많이 넣으면서, 1이 포함되지 않도록 조절하면 답을 구할 수 있다.