[백준] 15990번 : 1, 2, 3 더하기 5

Problem 🔒

문제

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

 

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

• 1+2+1
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

예제 입력 1

3
4
7
10

예제 출력 1

3
9
27

---

Approach ⭕

이 문제는 동적 프로그래밍(DP)을 활용하여 풀 수 있다.

1. 점화식 유도 과정
   • 조건에서 같은 수를 두 번 이상 연속해서 사용하면 안된다는 것이 포인트다.
   • 수 i를 만들 때, 해당 수식이 1,2,3으로 끝나는 개수를 각각 저장해야한다.
     • dp[i][1] : 수 i를 만들고 수식이 1로 끝나는 경우
     • dp[i][2] : 수 i를 만들고 수식이 2로 끝나는 경우
     • dp[i][3] : 수 i를 만들고 수식이 3으로 끝나는 경우
2. 점화식
   1. 수 N을 만들 때 해당 수식이 1로 끝나는 경우의 수
      • 일단, 연속해서 1을 사용할 수 없으므로, 직전에는 2또는 3이 사용되었어야 한다.
      • 그럼 수 (N-1)에서 수식이 2, 3으로 끝나는 경우에 1을 더해주면 된다.
   2. 수 N을 만들 때 해당 수식이 2로 끝나는 경우의 수
      • 마찬가지로 직전에는 1 또는 3이 사용되었어야 한다.
      • 수 (N-2)에서 수식이 1, 3으로 끝나는 경우에 2를 더해주면 된다.
   3. 수 N을 만들 때 해당 수식이 3으로 끝나는 경우의 수 
      • 직전에는 1 또는 2가 사용되었어야 한다.
      • 수 (N-3)에서 수식이 1, 2로 끝나는 경우에 3을 더해주면 된다.
3. long 타입 배열 사용
   • 항상 1000000009로 나눈 나머지를 저장하여 int 배열로 저장해도 문제 없을 것 같다.
   • 하지만, 중간에 값을 더하는 연산 과정에서 int 범위를 벗어나면 오버플로우가 발생할 수 있다.

$dp[N][1]=dp[N−1][2]+dp[N−1][3]$

$dp[N][2]=dp[N−2][1]+dp[N−2][3]$

$dp[N][3]=dp[N−3][1]+dp[N−3][2]$

위 점화식을 통해 N≥4이므로, N=1,2,3은 초기값으로 설정해줘야한다.

Learned 😯

• 아직 dp에 익숙하지 않아서, 점화식 유도하는게 어려워 답안을 보고 풀 수 있었다.
• 연산 과정에서 int 범위를 벗어나면 오버플로우가 발생한다는 것을 알게 되었다.

---

Solution 💡

public class Main {
    static int T, N;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        long[][] map = new long[100001][3];
        map[1][0]=1; map[2][1]=1; map[3][0]=1; map[3][1]=1;
        map[3][2]=1; map[4][0]=2; map[4][2]=1;
        for(int i=4; i<map.length; i++){
            map[i][0] = (map[i-1][1] + map[i-1][2])%1000000009;
            map[i][1] = (map[i-2][0] + map[i-2][2])%1000000009;
            map[i][2] = (map[i-3][0] + map[i-3][1])%1000000009;
        }
        while(T-->0){
            N = Integer.parseInt(br.readLine());
            sb.append((map[N][0] + map[N][1] + map[N][2])%1000000009).append("\\n");
        }//T
        System.out.println(sb);
    }
}