1. Problem 📃

[ 1, 2, 3 더하기 ]

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

[ 문제 ]

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

2. Input ⌨️

[ 입력 ]

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

3. Output 🖨

[ 출력 ]

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

4. Example 📚

[ 입출력 예시 ]

5. Solution 🔑

친구와 어떻게 풀까 고민해봤다.
"이런 문제는 규칙성이 보일 것이다"라는 친구의 말로 찾아보기로했다.

아직 풀지 못한 분이 있다면 우선 종이에 1부터 6까지 다 적어보고 규칙을 찾아본다면 풀기 쉬울 것이라 생각합니다.

---

1. 규칙을 찾아본다면 1은 1개, 2는 2개, 3은 4개, 4는 7개, 5는 13개, 6은 24개가 나온다. 보면 자기 자신의 앞의 수 3개의 1, 2, 3 더하기 개수를 합해주면 해당 값의 1, 2, 3 더하기 개수가 나온다.
   
   
2. 이를 클래스3에 피보나치 수에 있는 다이나믹 프로그래밍을 이용해서 풀 것이다.
   
   
3. 테스트케이스(T)를 입력 받고, 1, 2, 3 더하기를 찾을 정수(n)값을 입력한다.
   기존의 1, 2, 3의 개수는 쉽게 찾을 수 있으므로 미리 정의해두고 메서드(Search)를 호출한다.
   
   
4. 찾을 정수(n)이 3이하의 수라면 배열(dp)에 담긴 값을 바로 출력하고 그렇지 않다면,
   dp의 배열이 null값이라면(찾아보지 않은 수라면) (n-1), (n-2), (n-3)의 메서드를 각각 호출해서 더해주고 값이 구해진 dp[n] 값을 반환해준다.

6. Code 💻

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static Integer[] dp = new Integer[12];
	
	
	public static int Search(int val) {
		if(val<=3) {
			return dp[val];
		}
		else if(dp[val] == null){
			
			return Search(val-1) + Search(val-2) + Search(val-3);
		}
		
		return dp[val];
	}
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		
		for(int i=0; i<T; i++) {
			int a = Search(Integer.parseInt(br.readLine()));
			System.out.println(a);
		}

	}

}