👀 문제
https://www.acmicpc.net/problem/9461
👊 도전
1. 설계
- DP의 Bottom-Up 방식으로 이용한다.
- Memorization 기법 사용을 위해 배열을 둔 뒤, 작은 문제부터 해결해내가며 값을 저장하고, 중복호출 시 메모리 값을 재활용한다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;
/**
*
* @author HEESOO
*
*/
public class Main {
public static void main(String[] args){
Scanner input=new Scanner(System.in);
int t=input.nextInt();
int n;
long[] array=new long[101];
array[1]=1;
array[2]=1;
array[3]=1;
for(int i=4;i<=100;i++){
array[i]=array[i-2]+array[i-3];
}
for(int i=0;i<t;i++){
n=input.nextInt();
System.out.println(array[n]);
}
}
}
3. 결과
🤟 성공 🤟
처음에는 n을 입력받을 때 마다 새로 array[n+1]를 할당하여 1부터 n까지 구한 후 리턴하였는데, 런타임 에러가 발생하였다. 그래서 array를 100까지 먼저 구한 후, n에 따른 정답을 출력하는 형식으로 바꿨다. 근데 시간초과도 아니고 왜 런타임 에러인지 잘 모르겠다. 그래서 이상한 곳에서 헤맸다^_^..
4. 설명
- 점화식을 도출한다.
- 1 1 1 2 2 3 4 5 7 9를 보면, f(n)=f(n-2)+f(n-3) 점화식을 유추할 수 잇다.
- 따라서 f(4)부터 값을 계산할 수 있으므로, array[1]=array[2]=array[3]=1로 값을 저장한 후, 4부터 for문으로 Bottom-Up 방식으로 계산한다.
- 100까지 array 값을 먼저 계산한 후, 입력받은 n에 따른 array[n]을 리턴한다.
- array는 long타입이어야한다.
- int형 배열을 선언하면 100을 넣었을때 음수값이 나오는 것을 통해 오버헤드가 발생했음을 알 수 있다.
- 따라서, long형으로 선언하여 오버헤드를 방지한다.
👏 해결 완료!
다른사람은 f(n)=f(n-1)+f(n-5) 점화식을 이용했던데, 그것보단 n-2, n-3이 더 알기 쉬운 듯 하다.