15988.123더하기3

문제

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

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

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

## 입력

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

## 출력

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초 (추가 시간 없음)	512 MB	30097	10989	8392	34.724%

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

풀이

알고리즘 흐름

n=1 일때, 1

n=2 일때, 1+1 2

n=3 일때, 1+1+1 1+2 2+1 3

n=4 일때, 1+1+1+1 / 1+1+2 / 1+2+1 / 2+1+1 / 2+2 / 1+3 / 3+1

n=4를 자세히 들여다보면 3일때의 방법에 +1을 한값들이 보이고, 2일때의 방법에 +2 한 값들이 보이고, 1일때의 값에 +3한 값들이 보인다. 이를 통해 점화식을 구하면

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

여기까지가 이전에 풀었던 문제와 같은 방식으로 푸는 것이고, 문제를 보면 n은 양수이며 1,000,000보다 작거나 같다.의 조건이 있다.

n이 1,000,000 까지 범위라면, dp점화식을 채우는 덧셈을 생각해보자.
피보나치를 구할때 n=47일때부터 int의 범위를 초과한다.
즉, 나머지연산을 하기전의 (dp[i-1] + dp[i-2] + dp[i-3]) 의 값이 1000000009 x 1000000009 가 나올수 있는 것이므로 long으로 해결한다.

코드

package 기초1.Day19.정해영;  

import java.util.Scanner;  

public class _123더하기3 {  

    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);  

        int t = sc.nextInt();  

        long[] dp = new long[1_000_001];  

        //이전에 풀었던 123더하기 문제와 동일한데 고려할점이 있다.  
        //1. 제한 범위가 생김. > 모듈러 연산.  
        //n이 1,000,000 까지 범위라면, dp점화식을 채우는 덧셈을 생각해보자.  
        //피보나치를 구할때 n=47일때부터 int의 범위를 초과한다.  
        //즉, 나머지연산을 하기전의 (dp[i-1] + dp[i-2] + dp[i-3]) 의 값이 1000000009 x 1000000009 가 나올수 있는 것이므로  
        //long으로 해결한다.  

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

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

        for(int i=0; i<t; i++){  
            int n = sc.nextInt();  
            System.out.println(dp[n]);  
        }  
        sc.close();  
    }  
}