[백준 15988] 1, 2, 3 더하기 3 (자바)

백준 15988번 1, 2, 3 더하기 3 (자바)

 

 

 

출처

www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 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

 

 

 

접근 방법

1, 2, 3 더하기 첫 번째 문제와 거의 똑같다.

입력에 n의 조건이 하나 추가된 것이다.

저 범위를 감당할 수 있으려면 int가 아니라 long으로 배열을 선언해야 한다.

점화식은 이전 문제와 동일하다.

 

점화식 : dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

 

 

 

내 코드

package practice;

import java.util.Scanner;

public class OneTwoThreeSum3 {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		long[] result = new long[n];
		long[] dp = new long[1000001];
		
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		
		int num = 0;
		for (int i=0; i<n; i++) {
			num = sc.nextInt();
			
			if (num > 3) {
				for (int j=4; j<=num; j++) {
					dp[j] = (dp[j-1] + dp[j-2] + dp[j-3])%1000000009;
				}
			}
			
			result[i] = dp[num];
		}
		
		for (long i : result) {
			System.out.println(i);
		}
	}
}

 

 

 

고려할 점

1. 규칙을 찾아 점화식을 세울 것

2. 직접 써보며 규칙을 찾을 것

3. 제한에 따른 범위를 생각할 것