👨‍🏫 문제

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

입력

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

출력

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

예제 입력 1

3
4
7
10

예제 출력 1

7
44
274

⭕ 풀이

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

public class Solution_9095 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		int[] dp = new int[11];
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < T; i++) {
			int N = Integer.parseInt(br.readLine());
			
			for(int j = 4; j <= N; j++) {
				dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];
			}
			
			sb.append(dp[N]).append("\n");
		}
		
		System.out.println(sb.toString());
		
	}

}

💬 정리

- 이 문제는 동적계획법(Dynamic Programming) 기법 중 하나인 메모이제이션(Memoization)을 사용해야하는 문제..!!
- 여기서 규칙이 있다는 걸 볼 수 있다.

• n = 1 일 때,
  1
  한 가지이므로 dp[1] = 1 이다.
• n = 2 일 때,
  1 + 1
  2
  두 가지이므로 dp[2] = 2 이다.
• n = 3 일 때,
  1 + 1 + 1
  2 + 1
  1 + 2
  3
  총 4가지이므로 dp[3] = 4 이다.
• n = 4 일 때,
  1 + 1 + 1 +1
  2 + 1 + 1
  1 + 2 + 1
  3 + 1
  1 + 1 + 2
  2 + 2
  1 + 3
  총 7가지이므로 dp[4] = 7 이다.

하지만, n = 4 인 경우의 수에서 아래의 밑줄친 부분의 연산은 dp[3]에 포함된 경우의 수와 같다.

1 + 1 + 1 +1
2 + 1 + 1
1 + 2 + 1
3 + 1
아래의 밑줄친 부분의 연산 역시 dp[2]에 포함된 경우의 수와 동일하다.
1 + 1 + 2
2 + 2
아래의 밑줄친 부분의 연산은 dp[1]에 포함된 경우의 수이다.
1 + 3

여기서 얻을 수 있는 점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 이 된다.

※ 아직 갈길이 멀다...!