[백준 9095] 1, 2, 3 더하기 (JAVA)

백준 9095번 문제 - 1, 2, 3 더하기

9095번: 1, 2, 3 더하기

---

문제 분석

 

• 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 개수를 출력해라.
• n은 양수이며 11보다 작다.

---

 

해결 키 포인트

 

• DP로 구현
  • DP가 아니면 시간초과 발생 → 시간 제한 1초 BUT test case가 몇개 주어질지 제한이 없기 때문에 매우 빠른 속도여야 함
• 1부터 11까지 1을 만드는데 걸리는 시간 DP로 풀기
  • 쉽게 알 수 있는 dp 값 : dp[1] = 1 (1) | dp[2] = 2 (1+1, 2)
  • 추가적으로 dp[0] = 1로 초기화
    WHY? dp[3]을 확인할 때, dp[i-3] = dp[0] 도 더하는데 이 때 dp[3]은 3으로 만들 수 있는 경우가 1개 존재하므로 이를 제공하기 위해 dp[0]를 1로 설정
    
  • 3부터 11까지 dp 구하기 반복 : dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

 

---

코드

 

import java.io.*;

public class Main {
    public static int [] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        dp = new int[12];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < 12; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

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

        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            bw.write(dp[N] + "\n");
        }

        bw.flush();
        bw.close();
    }
}