백준 9095번 : 1, 2, 3 더하기

 문제

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

9095 1, 2, 3 더하기

 

 구현 방법

 점화식을 구해준 다음 bottom-up 방식으로 반복문을 돌려 구해주었습니다.

n이 1일 때 1, n이 2일 때 2, n이 3일 때 4, n이 4일 때 7이므로 n일 때 dp[n] = dp[n-1]+dp[n-2]+dp[n-3] 임을 알 수 있습니다.

 

 구현 코드

package BOJ.Silver;

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

public class BOJ9095_123더하기 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for (int tc=1;tc<=TC;tc++) {
			int N = Integer.parseInt(br.readLine());
			int[] dp = new int[N+1];
			dp[1] = 1;
			if(N>1) dp[2] = 2;
			if(N>2) dp[3] = 4;
			for (int i=4;i<=N;i++) {
				dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
			}
			sb.append(dp[N]+"\n");
		}
		System.out.println(sb);
	}
}

 

정답!