[백준]9095 - 1, 2, 3 더하기 문제 풀이(Java,자바)

9095번: 1, 2, 3 더하기

 

 

들어가며 

이 문제는 점화식을 구하면 풀리는 dp 문제입니다.

 

코드

package solved.ac.class3;

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

public class 백준9095_123더하기 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(reader.readLine());
        int[] dp = new int[13];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for (int i = 4; i <= 12; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(reader.readLine());
            result.append(dp[n]).append("\n");
        }
        System.out.println(result);
    }
}

풀이법

n일 때, 하나씩 결과값을 나열한 모습입니다.

1 - 1
2 - 2
3 - 4
4 - 7
5 - 13
6 - 24
7 - 44

 

잘 보시면 n-1, n-2, n-3 을 다 더하면 n이 되는 것을 확인하실 수 있습니다.

따라서 점화식을 도출할 수 있습니다.