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

풀이

• dp 배열을 선언하여 구현, dp[i]에는 i를 만들 수 있는 개수가 저장된다.

• dp[1] = 1, dp[2] = 2, dp[3] = 4 로 초기화한다.
  (1 / 1+1, 2 / 1+1+1, 1+2, 2+1, 3)

• 밑의 내용처럼 진행되므로 점화식은 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

n=4 일때
  - 1+3 -> 1 + 3만들수 있는 개수(dp[3])
  - 2+2 -> 2 + 2만들수 있는 개수(dp[2])
  - 3+1 -> 3 + 1만들수 있는 개수(dp[1])
n=5 일때
  - 1+4 -> 1 + 4만들수 있는 개수(dp[4])
  - 2+3 -> 2 + 3만들수 있는 개수(dp[3])
  - 3+2 -> 3 + 2만들수 있는 개수(dp[2])
n=6 일때
  - 1+5 -> 1 + 5만들수 있는 개수(dp[5])
  - 2+4 -> 2 + 4만들수 있는 개수(dp[4])
  - 3+3 -> 3 + 3만들수 있는 개수(dp[3])

코드

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

public class Main_S3_9095_123더하기 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			int n = Integer.parseInt(br.readLine());
			int[] dp = new int[n+1];
			
			for (int i = 1; i < n+1; i++) {
				if(i==1) dp[i] = 1;
				else if(i==2) dp[i] = 2;
				else if(i==3) dp[i] = 4;
				else {
					dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
				}
			}
			sb.append(dp[n]+"\n");
		}
		
		System.out.println(sb);
	}

}