DP문제..! 다이나믹 프로그래밍 문제인데,
큰 문제를 작은 문제로 나눌 수 있고, 부분 문제가 반복적으로 해결된다.
DP를 구현하는 방법은 상향식과 하향식이 있는데,
상향식은 작은 문제를 하나씩 해결하면서 먼저 계산했던 문제를 이용해서 다음 문제도 해결하는 것이고,
하향식은 미리 한번에 계산해서 메모리에 저장해놓고, 같은 문제를 호출하면 바로 결과를 가져오는건데 이런걸 메모이제이션이라고 한다.
0일때는 0이 1, 1이 0
1일때는 0이 0, 1이 1
2일때는 0이 1, 1이 1
3일때는 0이 1, 1이 2
4일때는 0이 2, 1이 3
.
.
.
이런식으로 이어지는데, 잘 보면 여기에 규칙이 있다.
2이후부터는 각각 전과, 전전 값을 더하면 값이 나온다는 것이다.
그러니까 2일때 0은 0일때 0이 나온 횟수 + 1일때 0이 나온 횟수
3일때는 0은 1일때 나온 횟수 + 2일때 0이 나온 횟수가 된다.
1의 값도 한 칸 앞으로 밀렸을 뿐 마찬가지이다.
이걸 이용해서 배열에 미리 계산을 전부 해놓고, 값이 입력될 때마다 저장된 값을 꺼내어 출력한다.
|
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
30
31
32
33
34
35
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[45];
arr[0]=0;
arr[1]=1;
for(int i=2;i<45;i++){
arr[i]=arr[i-2]+arr[i-1];
}
for(int i=0;i<N;i++) {
int req = Integer.parseInt(br.readLine());
if (req == 0)
System.out.println("1 0");
else if (req == 1)
System.out.println("0 1");
else {
System.out.println(arr[req - 1] + " " + arr[req]);
}
}
}
}
|
cs |