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

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

 

 

 

출처

www.acmicpc.net/problem/9095

9095번: 1, 2, 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은 양수이며 11보다 작다.

 

 

 

출력

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

 

 

 

입출력 예

입출력 예 1

 

 

 

접근 방법

이 문제는 문제에 주어진 규칙을 일단 1부터 5까지 직접 나열해 보면 규칙을 찾을 수 있다.

n=1 -> 1 -> 1개

n=2 -> 11, 2 -> 2개

n=3 -> 111, 12, 21, 3 -> 4개

n=4 -> 1111, 112, 121, 211, 13, 31, 22 -> 7개

....

위 순서를 보면 4는 1+2+4를 더한 값이란 것을 파악할 수 있다.

따라서 점화식은 피보나치와 비슷하게 아래와 같이 세울 수 있다.

 

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

 

앞에 2개의 항은 먼저 들어가 있어야 뒤 연산이 가능하므로 직접 넣어놓고 연산에 활용하며 보텀업으로 나아간다.

 

 

 

내 코드

package practice;

import java.util.Scanner;

public class OneTwoThreeSum {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int[] result = new int[n];
		int[] dp = new int[11];
		
		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];
				}
			}
			result[i] = dp[num];
		}
		
		for (int i : result) {
			System.out.println(i);
		}
		
	}//main
}

 

 

 

고려할 점

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

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