백준 9095번(DP) : 1, 2, 3 더하기 (JAVA) 문제 풀이

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

9095번: 1, 2, 3 더하기

 

---

✏️ 문제

 

---

🔐 문제 해결

1. 테이블 정의하기

테이블은 dp[i]를 1,2,3으로 표현할 수 있는 횟수로 설정하겠습니다.

 

2. 점화식 구하기

먼저 dp[4]는 본문에도 나와있듯이 아래와 같이 총 7가지가 있습니다.

이것을 1, 2, 3으로 나눠서 생각해보자면,

• 하나의 숫자를 3로 고정하고, 나머지 1을 1, 2, 3으로 조합하는 경우
  • 1 + 3
• 하나의 숫자를 2로 고정하고, 나머지 2를 1, 2, 3으로 조합하는 경우
  • 1 + 1 + 2
  • 2 + 2
• 하나의 숫자를 1로 고정하고, 나머지 3을 1, 2, 3으로 조합하는 경우
  • 1 + 1 + 1 + 1
  • 1 + 2 + 1
  • 2 + 1 + 1
  • 3 + 1

dp[4] = dp[1] + dp[2] + dp[3];
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

 

3. 초기값 세팅

초기값은 위에서 dp[4]를 구한 과정에서 얻은 값들을 아래와 같이 세팅할 수 있습니다.

dp[1] = 1;
dp[2] = 2;
dp[3] = 3;

 

 

---

🗝 전체 코드

import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();

        int[] dp = new int[12];

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for(int i=4; i<= 11; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }

        int N = Integer.parseInt(bf.readLine());

        for(int i=0; i<N; i++){
            sb.append(dp[Integer.parseInt(bf.readLine())] + "\n");
        }

        System.out.print(sb.toString());
    }
}