[BOJ15991] 1,2,3더하기 6(동적 프로그래밍)

 

---

문제 링크 

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

15991번: 1, 2, 3 더하기 6

---

풀이 

시간 복잡도 : O(N)

 

문제)

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

단, 합은 대칭을 이루어야 한다.

 

1 + 1 + 1 + 1

1 + 2 + 1

2 + 2

 

 

대칭을 이루는게 포인트이기 때문에 아래와 같이 구하면 되었다

- DP[N - 2] 양 옆에 1씩 더하는 경우 

- DP[N - 4] 양 옆에 2씩 더하는 경우 

- DP[N - 6] 양 옆에 3씩 더하는 경우

 

초기화는 DP[1] ~ DP[6] 까지 설정하였다

초기화에서 실수를 했는데 6의 경우 3 + 3 이 대칭을 이뤄서 6개가 되었다

 

 

점화식 

DP[N] = (DP[N - 2] + DP[N - 4] + DP[N - 6]) % MOD

---

제출 코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();
    static String NEW_LINE = System.lineSeparator();
    static int MOD = 1000000009;
    
    static int T, N;
    static long[] DP = new long[100001];

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

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

            sb.append(DP[N]).append(NEW_LINE);

            T -= 1;
        }

        output();
    }

    private static void preprocess() {
        // 초기화
        DP[1] = 1;
        DP[2] = 2;
        DP[3] = 2;
        DP[4] = 3;
        DP[5] = 3;
        DP[6] = 6;

        for(int i = 7; i <= 100000; i++) {
            DP[i] = (DP[i - 2] + DP[i - 4] + DP[i - 6]) % 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());
        }

    }
}