숫자를 분해한 후 얻을 수 있는 숫자들의 곱을 최대화하는 문제이다.
당연하게도 많은 수를 곱하는것이 이득임은 쉽게 알 수 있다.
그럼 최대한 많은 수를 곱을 최대화하는 것이 관건이 된다.
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이 포함되지 않도록 조절하면 답을 구할 수 있다.
'BOJ' 카테고리의 다른 글
BOJ 20194 - 경계 로봇 (2) | 2024.01.31 |
---|---|
BOJ 17433 - 신비로운 수 (0) | 2024.01.27 |
BOJ 2014 - 소수의 곱 (1) | 2024.01.23 |
BOJ 17612 - 쇼핑몰 (1) | 2024.01.22 |
BOJ 30397 - 대구과학고등학교 (1) | 2023.11.14 |