BOJ/15990) 1, 2, 3 더하기 5

1, 2, 3 더하기(15990), Silver2

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

문제풀이

1, 2, 3 더하기1(9095)과 같은 문제이지만, 같은 수를 두 번 이상 연속해서 사용해서는 안된다는 조건이 있기 때문에 마지막 자리 숫자에 관한 정보를 저장해야 한다.
따라서 탐색 중인 정수 N과 마지막 자리 숫자 K의 정보를 가진 2차원 배열 DP[N][K]을 이용해 문제를 해결하였다.
예를 들어서 DP[3][1]은 정수 3을 1, 2, 3의 합으로 나타낸 방법 중 마지막이 1로 끝나는 경우의 수를 의미한다.

🤔 기본값 설정

우선 정수 N의 값이 1, 2, 3인 경우는 기존 정수들과 다르게 예외가 존재하기 때문에 따로 설정을 해줘야 한다.

• N == 1
  1 -> DP[1][1] = 1
• N == 2
  2 -> DP[2][2] = 1
• N == 3
  2+1 -> DP[3][1] = 1
  1+2 -> DP[3][2] = 1
  3 -> DP[3][3] = 1

🤔 같은 수를 연속해서 사용하지 않는 법

정수 N이 4인 경우를 생각해보자. 4를 1, 2, 3의 합을 통해 만드는 경우는 세 가지가 있다.

1. DP[4-3][K] 의 경우에서 각 1을 더한 경우
2. DP[4-2][K] 의 경우에서 각 2를 더한 경우
3. DP[4-1][K] 의 경우에서 각 3을 더한 경우

• DP[4][1] - 1+2+1, 2+1+1, 3+1
• DP[4][2] - 2+2
• DP[4][3] - 1+3

이때 연속되는 수가 발생해서는 안되기 때문에 k를 더한 경우를 구할 때는 마지막 자리가 k로 끝나는 값들은 제외해야 한다.

• DP[4][1] - DP[3][1] + DP[3][2] + DP[3][3]
• DP[4][2] - DP[2][1] + DP[2][2] + DP[2][3]
• DP[4][3] - DP[1][1] + DP[1][2] + DP[1][3]

따라서 도출 가능한 점화식은 다음과 같다.

DP[i][1] = (DP[i-1][2] + DP[i-1][3]) % 1,000,000,009
DP[i][2] = (DP[i-2][1] + DP[i-2][3]) % 1,000,000,009
DP[i][3] = (DP[i-3][1] + DP[i-3][2]) % 1,000,000,009 (n >= 4)

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static final int NUM = 1000000009;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        long[][] 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;

        for(int i = 4; i <= 100000; i++) {
            dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % NUM;
            dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % NUM;
            dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % NUM;
        }

        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            long answer = (dp[n][1] + dp[n][2] + dp[n][3]) % NUM;
            System.out.println(answer);
        }
        br.close();
    }
}

후기

문제를 읽고 2차원 배열과 DP를 활용해서 문제를 풀어야겠다는 판단이 들기에는 아직 부족한 듯 하다.