15990.123더하기5

문제

정수 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 초 (추가 시간 없음)	512 MB	26395	8918	6250	30.858%

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

풀이

알고리즘 흐름

이문제로 한참을 고민했다... dp를 사용해서 1차원 배열을 만들고 아무리 생각을 해봐도 안풀리는 것이다. 내가 고민을 하다가 안풀렸던 부분이 만약 3일 경우 1+1+1, 1+2, 3 이렇게 3가지의 경우가 생기고, 제일 뒷자리가 1일때, 2일때, 3일때를 구분지어주는 부분을 어떻게 구현할지 도저히 감이 안왔다. 그래서 찾아보니... 오마갓 진짜 사람들 똑똑해😂

자그럼 문제를 풀어보자!

이문제는 일단 DP와 2차원 배열을 사용해야한다.

DP 문제이므로 먼저 공통점을 찾아 내는것이 중요하다. 문제를 작은 단위부터 천천히 훑어 보았다.

1 > 1
2 > 1+1, 2
3 > 1+1+1, 2+1, 1+2, 3
4 > (1+1+1+1, 2+1+1, 1+2+1, 3+1), (1+1+2, 2+2), (1+3)

이정도면 이제 어느정도 공통점이 보여야한다.

• 4를 만들때, 3을 만드는 경우 +1
• 4를 만들때, 2를 만드는 경우 +2
• 4를 만들때, 1을 만드는 경우 +3
  (여기에서 2번이상 중복되는 부분을 제거하고 dp에 기록하면 되겠구나.)

이를 바탕으로 dp를 나타내보면,

dp[i][j]    // i: 임의의 정수, j: 덧셈이 j로 끝남

이렇게 보면 되겠다. 그럼 예시를 들어보자.

3을 만드는 경우

• 1+1+1 => dp[3][1] = 1
• 1+2 => dp[3][2] = 1
• 2+1 => dp[3][1] = 1
• 3 => dp[3][3] = 1

5를 만드는 경우

5를 만드는 경우를 자세하게 알아보자.

5를 1, 2 ,3 의 합으로 나타내보자.
2를 만드는 경우에 3을 더하고,
3을 만드는 경우에 2를 더하고,
4를 만드는 경우에 1을 더하면 5가 될것이다.
(이때 같은 수를 2번 연속으로 사용할수는 없다. 즉, 이전에 사용한 값은 제거한다.)

1) 5를 만드는 수식중에
1로 끝나는 수식(마지막에 1을 더해주는 경우)은
4를 만드는 수식에서 2로 끝나는 것에 1를 더하는것,
4를 만드는 수식중에서 3으로 끝나는 것에 1을 더하는 것이다.
(같은 수 연속 2번은 안되기 때문에 1로 끝나는 것을 제외한다.)
이를 나타내보면 아래와 같다.

dp[5][1] = dp[4][2] + dp[4][3];

// 이것을 일반화 하면 아래와 같다.

dp[n][1] = dp[n-1][2] + dp[n-1][3];

2) 2를 더하는 경우를 살펴보자
마지막에 2를 더해주는 경우는,
3을 만드는 수식에서 1로 끝나는 것에 2를 더하는것,
3을 만드는 수식에서 3으로 끝나는 것에 2를 더하는 것이다.
(이것 또한 같은 수를 연속으로하면 안되므로 2로 끝나는 것은 제외 된다.)

dp[5][2] = dp[3][1] + dp[3][3];

// 이것을 일반화 하면 아래와 같다.

dp[n][1] = dp[n-2][1] + dp[n-2][3];

3) 3을 더하는 경우를 살펴보자
마지막에 3을 더해주는 경우는,
2를 만드는 수식에서 1로 끝나는 것에 3을 더하는것,
2를 만드는 수식에서 2로 끝나는 것에 3을 더하는것이다.
(이것도 같은 수를 연속으로 나열할수없으므로 3으로 끝나는 것은 제거한다.)

dp[5][3] = dp[2][1] + dp[2][2];

// 이것을 일반화 하면 아래와 같다.

dp[n][3] = dp[n-3][1] + dp[n-3][2];

이러한 과정을 통해 결과적으로 점화식을 도출해 낼수있다.

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)

점화식에서 모듈러를 사용하는 이유
10억9로 나눠서 출력하라는 제한 사항이 있는데, 마지막에 모듈러를 넣게되면 값이 정상적으로 출력되지않는다. 그러므로 계산 과정 중간에 모듈러를 삽입한다.

코드

import java.util.Scanner;  

public class _123더하기5 {  

    public static void main(String[] args) {  

        Scanner sc = new Scanner(System.in);  

        int t = sc.nextInt();  

        long[][] dp = new long[100001][4];  

        dp[1][1] = 1; // 1  
        dp[2][2] = 1; // 2  
        dp[3][1] = 1; // 2+1  
        dp[3][2] = 1; // 1+2  
        dp[3][3] = 1; // 3  

        for(int i=4; i<=100000; i++){  
            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;  
        }  

        for(int i=1; i<=t; i++){  
            int n = sc.nextInt();  
            System.out.println((dp[n][1] + dp[n][2] + dp[n][3]) % 1_000_000_009);  
        }  

        sc.close();  
    }  
}