[백준][자바] 9095 - 1, 2, 3 더하기 - DP

📌 문제

백준 | 1, 2, 3 더하기 | SILVER 3 | DP

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

 

 

 

📌 문제 탐색하기

• n이 있을 때, 1,2,3의 합으로 나타내는 방법의 수를 찾기
• 합은 1개 이상 사용해야한다.

 

 

 

📌 알고리즘

• 방법이 존재하는 경우들을 모두 세야하므로, DP를 활용해야한다.
• DP는 그 이전의 결과값을 바탕으로 쓸 수 있으므로, 해당 값을 이용해야한다.

DP[0] = 0

DP[1] = 1

DP[2] = 2

DP[3] = 4

DP[4] = 7 (=1+2+4)

DP[5] = 13 (=2+4+7)

DP[6] = 24 (=4+7+13)

DP[7] = 44 (=7+13+24)

DP[10] = 274

 

즉, DP[i] = DP[i-1] + DP[i-2] +DP[i-3] (i ≽ 4)

 

📌 코드 설계하기

1. t, 케이스 입력
2. dp 배열 구현
3. t 케이스에 따른 답변 출력

 

📌 정답 코드

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

public class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());

        int[] dp = new int[12];
        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];
        }

        for (int i = 0; i < t; i++) {
            int num = Integer.parseInt(br.readLine());
            System.out.println(dp[num]);
        }
    }
}

 

이전에 풀어봤던 문제랑 비슷해서, 생각보다 빠르게 풀 수 있었다!

DP는 진짜.. 알고리즘 싸움보단 수학적 사고를 어떻게 빠르게 하냐의 싸움인 것 같아 문제를 많이 풀어야겠다 😂