[백준 9095번] 1, 2, 3 더하기(Java)

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

9095번: 1, 2, 3 더하기

실버 3이며,  동적할당을 이용해서 푸는 문제입니다

---

풀이

만약 n이 주어진다면 저 n을 1,2,3의 합으로 나타내는 경우를 모두 구해 주면 됩니다. 처음 생각해보면 꽤 시간이 많이 걸릴것 같지만 푸는 방법만 알면 어렵지 않습니다

동적 계획은 이전에 저장 되어있는 값을 이용해 누적해서 계산해주는 방법입니다. 때문에, 만약 n이 1..3.까지 라고 했을때, dp[1] =1, dp[2]=2, dp[3]= 4입니다.  dp[0]은 0으로 둡시다. 0원을 만드는 경우의 수는 없으니까요

그러면 만약 n=4일때, 그러니까 dp[4]일때를 구한다 해봅시다. 그럼 식은 다음과 같습니다

1원을 마지막으로 사용했을때:  4  - 1 = 3, 그러니까 dp[3]인 경우의 수 입니다. 

2원을 마지막으로 사용 했을 때, 4 - 2 = 2, dp[2] 인 경우의 수입니다.

3원을 마지막으로 사용 했을 때, 4 - 3 = 1.dp[1]인 경우의 수 입니다.

 

따라서 dp[4]= dp[1] +dp[2]+dp[3]=1+2+4=7입니다. 이를 이용하면 점화식을 하나 구할 수 있습니다.

 dp[n]=dp[n-1]+dp[n-2]+dp[n-3] (n>=3) 

---

코드

import java.io.*;
public class Main {
	public static void main(String arg[]) throws NumberFormatException, IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
		
		int t=Integer.parseInt(br.readLine());
		int [] dp=new int[1000];
		int []n=new int[t];
		for(int i=0; i<t;i++) {
			n[i]=Integer.parseInt(br.readLine());
		}
		dp[0]=1;
		dp[1]=2;
		dp[2]=4;
		for(int i=0;i<t;i++) {
			for(int j=3; j<n[i];j++) {
				dp[j]=dp[j-1]+dp[j-2]+dp[j-3];
			}
			bw.write(String.valueOf(dp[n[i]-1])+"\n");
			
		}
		bw.flush();
		bw.close();
	}
}