문제 풀이
- 숫자 n이 주어졌을때 a+b+c+….+z=n (a,b,c는 자연수) abc…z의 최댓값을 구하는 문제
Code Snippets
public class test4 {
public static void main(String[] args) {
long start = System.currentTimeMillis();
int n=100;
System.out.println(Solution(n));
long end = System.currentTimeMillis();
System.out.println("실행시간 :"+(end-start/1000.0));
}
static long Solution(int n) {
// 각 n의 결과를 저장할 배열을 만든다.
long arr[]= new long[n+1];
// 배열 2,3은 유일하게 1*(n-1)이 최대이므로 defualt 입력
arr[2]=2;
arr[3]=3;
// n은 4부터 실행
for (int i = 4; i <= n; i++) {
int mid = i/2;
// mid를 기준으로 대칭이므로 중간까지만 본다.
for (int j = 2; j <=mid ; j++) {
arr[i]=Math.max(arr[i], arr[j]*arr[i-j]);
}
}
return arr[n];
}
}
Result
7412080755407364
실행시간 :1.591723736038909E12
앞에서 구한 최댓값을 뒤에 연산식에 활용하는 대표적인 메모이제이션 문제이다. mid를 사용하여 성능을 개선 하였으나 n자체가 크지 않아(결과값 오버플로우 발생하는 n의 값이 크지 않다.) 실행시간에 큰 차이는 없다.