[BOJ 15990] 1, 2, 3 더하기 5 (Java, DP)

 

 

---

문제 링크

https://www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

---

문제 풀이 

- 시간 복잡도 :  O(N)

- 1,2,3 더하기 문제에서 조금 변형된 문제, 상향식, 하향식 연습하기 좋은 문제

- 단, 같은 숫자를 연속적으로 붙일 수 없기 때문에 이전 숫자에서 무엇이 사용되었는지 상태값을 기록할 필요가 있다

(2차원 배열 사용)

- 간단하게 2차원 배열로 해서 1 ~ 3 숫자 사용 여부를 표기하고 동일하게 점화식으로 구하면 됨

- 최대치 long

 

 

DP[N + 1][4] 2차원 배열 생성 ( DP[N][1] : 숫자N을 만들때 마지막에 1이 더해진 경우의 수를 나타냄 )

1	2	3	4	5	6	7
1	2	2 + 1 1 + 2 3	1 + 2 + 1 3 + 1 1 + 3	1 + 3 + 1 2 + 1 + 2 3 + 2 2 + 3	2 + 1 + 2 + 1 3 + 2 + 1 2 + 3 + 1 1 + 2 + 1 + 2 3 + 1 + 2 1 + 3 + 2 2 + 1 + 3 1 + 2 + 3	1+2+1+2+1 3+1+2+1 1+3+2+1 2+1+3+1 1+2+3+1 1+3+1+2 2+3+2 2+1+3 1+2+3

 

 

 i = 5 일 때

① 끝에 1을 더해서 i를 만들려면 i - 1에서 2와 3으로 끝나는 경우의 수를 더해주면 된다

DP[i][1] = (DP[i - 1][2] + DP[i - 1][3]) % MOD;

 

② 끝에 2을 더해서 i를 만들려면 i - 2에서 1와 3으로 끝나는 경우의 수를 더해주면 된다

DP[i][2] = (DP[i - 2][1] + DP[i - 2][3]) % MOD;

 

③ 끝에 3을 더해서 i를 만들려면 i - 3에서 1와 2로 끝나는 경우의 수를 더해주면 된다 

DP[i][3] = (DP[i - 3][1] + DP[i - 3][2]) % MOD;

---

제출 코드

(1) Bottom-Up

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();

    static int MOD = 1000000009;
    static int T, N;
    static long[][] DP;


    public static void main(String[] args) throws IOException {
        bottomUp();

        T = inputProcessor.nextInt();
        while(T > 0) {
            N = inputProcessor.nextInt();

            long result = 0L;
            for(int i = 1; i <= 3; i++) {
                result += DP[N][i];
                result %= MOD;
            }

            sb.append(result).append("\n");
            
            T -= 1;
        }


        output();
    }

    private static void bottomUp() {
        DP = new long[100001][4];
        DP[1][1] = 1; 
        DP[2][2] = 1; 

        DP[3][1] = 1; 
        DP[3][2] = 1; 
        DP[3][3] = 1; 

        DP[4][1] = 2;
        DP[4][3] = 1;

        for(int i = 5; i <= 100000; i++) {
            DP[i][1] = (DP[i - 1][2] + DP[i - 1][3]) % MOD;
            DP[i][2] = (DP[i - 2][1] + DP[i - 2][3]) % MOD;
            DP[i][3] = (DP[i - 3][1] + DP[i - 3][2]) % MOD;
        }
    }


    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";
            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
    
}

 

 

(2) Top-Down

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();

    static int MOD = 1000000009;
    static int T, N;
    static long[][] DP;


    public static void main(String[] args) throws IOException {
        init();

        T = inputProcessor.nextInt();
        while(T > 0) {
            N = inputProcessor.nextInt();

            long result = 0L;
            for(int i = 1; i <= 3; i++) {
                result += topDown(N, i);
                result %= MOD;
            }

            sb.append(result).append("\n");

            T -= 1;
        }



        output();
    }

    private static long topDown(int n, int i) {
        if(n < 1) return 0L;
        if(DP[n][i] != -1) return DP[n][i];

        if(i == 1) {
            DP[n][1] = (topDown(n - 1, 2) + topDown(n - 1, 3)) % MOD;
        } else if(i == 2) {
            DP[n][2] = (topDown(n - 2, 1) + topDown(n - 2, 3)) % MOD;
        } else if(i == 3) {
            DP[n][3] = (topDown(n - 3, 1) + topDown(n - 3, 2)) % MOD;
        }

        return DP[n][i];
    }

    private static void init() {
        DP = new long[100001][4];
        DP[1][1] = 1; 
        DP[2][2] = 1; 

        DP[3][1] = 1; 
        DP[3][2] = 1; 
        DP[3][3] = 1; 

        DP[4][1] = 2;
        DP[4][3] = 1;

        for(int i = 5; i <= 100000; i++) {
            Arrays.fill(DP[i], -1);
        }
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";
            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
    
}