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

🧫 문제 분석

✔️ 출처

1, 2, 3 더하기 실버 3

 

📖 문제

 

 

DP(동적계획법) 문제이다.

 

우선 1 과 2 그리고 3을 구하는 경우의 수를 봐보자

 

1 

• 1

 

2

• 1 + 1
• 2

3

• 1 + 1 + 1
• 2 + 1
• 1 + 2
• 3

 

문제에서 예시로 4를 구하는 방법이 나와있다.

 

4를 구하는 방법은 크게 보면

• 1 + 3 
• 2 + 2
• 3 + 1 

이 세가지 경우라고 볼 수 있다. 우리는 1, 2, 3을 통해서 방법의 수를 구하기에 

1을 고정해놓고 3을 구하는 경우의 수

2를 고정해놓고 2를 구하는 경우의 수

3을 고정해놓고 1을 구하는 경우의 수

이 세가지의 합이 4를 구하는 경우의 수라고 볼 수 있다.

 

표로 보자면 이렇게 볼 수 있다.

고정	경우의 수
1 +	1 + 1 + 1 1 + 2 2 + 1 3
2 +	1 + 1 2
3 +	1

 

 

---

🔅 문제 풀이

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

public class Main {

    public static void main(String[] args) throws Exception {
        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 j = 4; j < 12; j++) {
            DP[j] = DP[j - 1] + DP[j - 2] + DP[j - 3];
        }

        for (int i = 1; i <= T; i++) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(DP[n]);
        }
    }
}

 

---

 

이 문제는 작년 11월에 시도했다가 못풀었어서 북마크해놨었는데 오늘 우연히 이 문제를 보게되서 풀었다. 

 

❗ 오답노트 / 필요한 지식

1. DP 문제를 풀때마다 여러가지 경우를 생각하게 되는 것 같다.