문제
음이 아닌 정수 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로 나눈 나머지를 출력한다.
문제풀이
일단 N의 모든 분할을 구해서 곱해서 max값을 찾는것은 말이 안된다. N이 1000000까지이기 때문에 말도 안되는 시간이 나온다.
N이 1000000이므로 N이나 NlogN정도의 시간이 걸리는 풀이를 찾아야 한다.
이 뜻은 1000000까지 한번 반복문을 돌린다고 했을때, 반복문 안에 들어갈 수 있는 구문은 상수시간이나, binary-search와 같은 logN이 걸려야 한다는 것이다.
시간에 대한 분석은 이정도면 된거같고, 문제를 살펴보면
N의 분할의 element를 전부 곱한게 가장 큰 경우 를 구하는 것이 문제이다.
4의 분할은 {1,1,1,1} {1,1,2}, {2,2} , {1,3}, {4}이고, 이럴 경우에 정답은 4가되게 된다.
4의 분할을 써본 후에, DP로 한번 접근하게 되었는데
이유는 4의 분할의 부분집합의 첫번째 요소가 1일때, 이 때의 최댓값은 1 * 3의 분할의 최댓값 이고, 2일때의 최댓값은 2 * 2의 분할의 최댓값이기 때문이다.
하지만 이렇게 풀이를 한다면 어떠한 N을 접근할때 N/2까지는 필수적으로 접근을 해야 하므로 1~N/2까지의 합 -> O(N^2)의 시간이 걸리게 된다.
여기서 이 문제는 다른 기법을 사용하는것 보다, 규칙을 찾는 것에 대한 냄새가 나서 1 ~ 10까지 한번 다 써보았다.
1 -> 1
2 -> 2
3 -> 3
4 -> 4 2^2
5 -> 6 23
6 -> 9 3^2
7 -> 12 2^2 3
8 -> 18 3^2 * 2
9 -> 27
10 -> 36
수열을 잘 생각해보면 이 수열들은 {2, 3}의 중복조합으로 이룰 수 있는 수의 오름차순이라고 볼 수 있다.
순차적으로 배열에 넣어서 DP로 풀었다.
#include <iostream>
using namespace std;
long long N, arr[1000001];
int main(){
cin>>N;
arr[1] = 1;
arr[2] = 2;
arr[3] = 3;
for(int i=4; i<=N; i++){
if(i%3==1){
arr[i] = arr[i-2]*2%10007;
}else if(i%3==2)
arr[i] = arr[i-2]*2%10007;
else
arr[i] = arr[i-3]*3%10007;
}
cout<<arr[N];
}