[백준] 15993번. 1, 2, 3 더하기 8(JAVA)

문제

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

---

풀이(12분)

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

public class Main {

    static final int MOD = 1_000_000_009;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        int[] nums = new int[T];
        int max = 0;
        for (int i = 0; i < T; i++) {
            nums[i] = Integer.parseInt(br.readLine());
            if (nums[i] > max) {
                max = nums[i];
            }
        }

        // max가 최소 4까지는 보장되도록 수정
        if (max < 4) {
            max = 4;
        }

        // dp[i][0]는 합이 i가 되는 경우의 수 중 홀수 개수로 이루어진 것
        // dp[i][1]는 합이 i가 되는 경우의 수 중 짝수 개수로 이루어진 것
        long[][] dp = new long[max + 1][2];

        // 초기값 설정
        dp[1][0] = 1; // 1
        dp[2][0] = 1; // 2
        dp[2][1] = 1; // 1+1
        dp[3][0] = 2; // 3, 1+1+1
        dp[3][1] = 2; // 1+2, 2+1
        dp[4][0] = 3; // 1+1+1+1, 1+3, 3+1
        dp[4][1] = 4; // 1+1+2, 1+2+1, 2+1+1, 2+2

        for (int i = 5; i <= max; i++) {
            // i-1, i-2, i-3에 1, 2, 3을 더해서 i를 만드는 경우
            // dp[i-1][1]는 i-1을 만드는 짝수개 항의 합
            // 여기에 1을 더하면 i를 만드는 홀수개 항의 합이 됨
            dp[i][0] = (dp[i - 1][1] + dp[i - 2][1] + dp[i - 3][1]) % MOD;

            // dp[i-1][0]는 i-1을 만드는 홀수개 항의 합
            // 여기에 1을 더하면 i를 만드는 짝수개 항의 합이 됨
            dp[i][1] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 3][0]) % MOD;
        }

        StringBuilder sb = new StringBuilder();
        for (int i : nums) {
            sb.append(dp[i][0]).append(" ").append(dp[i][1]).append("\n");
        }

        System.out.println(sb);
    }
}

---

문제 풀이 전략

 

💡 아이디어

1, 2, 3 을 더하여 N이라는 숫자를 만들 수 있는 방법은 3가지이다.

 

1. N - 1 + 1 = N

2. N - 2 + 2 = N

3. N - 3 + 3 = N

 

그렇다면 dp를 이용할 수 있겠구나!

---

🤔 풀이 고도화

그럼 홀수와 짝수에 대한 것은 어떻게 관리하지?

 

dp의 값을 홀수와 짝수로 구분해서 두어 이 전이 홀수인 경우 짝수로, 짝수인 경우 홀수로 가면 되겠다!!