Problem Solving/Java
백준 15990 1,2,3 더하기 5 동적계획법 활용 풀이 ( Java )
TakeKnowledge
2019. 10. 30. 20:41
반응형
15990번: 1, 2, 3 더하기 5
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
www.acmicpc.net
- Bottom-up 방식
|
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
public class Main {
static final long MOD = 1000000009L;
static final int LIMIT = 100000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
long[][] d = new long[LIMIT + 1][4];
// 값 저장할 배열 생성
// d[i][j] = i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j
// i로 0이 들어올 때의 케이스는 이미 배열 생성과 동시에 0, 0 , 0으로 세팅되어 있으니 바로 시작
for (int i = 1; i <= LIMIT; i++) {
if (i - 1 >= 0) {
d[i][1] = d[i - 1][2] + d[i - 1][3];
// 끝에 1이 올 경우
if (i == 1) {
// 1일 때 1이 오는 경우는 예외 처리
d[i][1] = 1;
}
}
if (i - 2 >= 0) {
d[i][2] = d[i - 2][1] + d[i - 2][3];
// 끝에 2가 올 경우
if (i == 2) {
d[i][2] = 1;
}
}
if (i - 3 >= 0) {
d[i][3] = d[i - 3][1] + d[i - 3][2];
// 끝에 3이 올 경우
if (i == 3) {
d[i][3] = 1;
}
}
d[i][1] %= MOD;
d[i][2] %= MOD;
d[i][3] %= MOD;
}
int times = Integer.parseInt(br.readLine());
// 테스트 케이스의 갯수 입력
for (int i = 0; i < times; i++) {
int n = Integer.parseInt(br.readLine());
// 입력
long answer = (d[n][1] + d[n][2] + d[n][3]) % MOD;
// 테스트 케이스 받고
// 출력
bw.write('\n');
}
}
}
|
연속을 처리해야하기 때문에 이차원 배열을 사용한다.
그러다보니 아직 1차원 배열로 재귀 호출로 구현하는 것도 머리가 아픈 나는 Top Down 방식은 나중으로 미루기로..
몇시간 붙잡고 있다가 포기했다 ㅜㅜ
반응형