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
import java.io.*;
 
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(String.valueOf(answer));
            // 출력
            bw.write('\n');
            bw.flush();
 
        }
 
    }
 
}

 

연속을 처리해야하기 때문에 이차원 배열을 사용한다.

 

그러다보니 아직 1차원 배열로 재귀 호출로 구현하는 것도 머리가 아픈 나는 Top Down 방식은 나중으로 미루기로..

 

몇시간 붙잡고 있다가 포기했다 ㅜㅜ

반응형