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

문제 링크

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

나의 기록

✅ 알고리즘 분류 : DP

✅ 성공 여부 : ✔

✅ 문제 난이도 : 실버3

✅ 체감 난이도 : Easy

접근 방법

DP의 기본적인 개념에 대해 가볍게 학습할 수 있는 문제.

DP 배열의 1,2,3에는 초깃값을 설정해주고, 나머지 숫자는 앞서 계산한 3개의 값을 더해주면 원하는 정답이 된다.

 

코드

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

public class bj9095_123더하기 {
    public static void main(String[] args) throws IOException {
        // DP 초깃값 입력
        int[] dp = new int[11];
        dp[1] = 1; dp[2] = 2; dp[3] = 4;

        // DP[i]는 이전 3개 경우의 합이다.
        for(int i = 4 ; i <= 10 ; i++){
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int t = 0 ; t < T ; t++){
            System.out.println(dp[Integer.parseInt(br.readLine())]);
        }
    }
}