[BOJ] 백준 9095 1, 2, 3 더하기 Java

1. 문제 요약

• 문제 URL : https://www.acmicpc.net/problem/9095
• 난이도 : 실버3
• 문제 내용 : n이 주어졌을 때, 정수 1, 2, 3을 더해서 n을 만드는 모든 방법의 수를 구하는 문제이다. 순서가 다른 경우는 다른 방법으로 취급한다.

2. 내 풀이 방법

• 시도1
  • 접근 방법
    • DP (Dynamic Programming) 이용하였다.
    • 점화식 계산 방법

    n	방법의 개수
    1	1
    2	1+1, 2 => 2
    3	1+1+1, 1+2, 2+1 => 3
    4	1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 => 7 = 4 + 2 + 1
    5	1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+1+3, 1+2+1+1, 1+2+2, 1+3+1,2+1+1+1, 2+1+2, 2+2+1, 2+3, 3+1+1, 3+2 => 13 = 7 + 4 + 2

  • 소스 코드

  import java.util.*;
  public class Main {
      public static void main(String[] args) {
          // n은 최대 10
          int[] dp = new int[11];
  
          // 초기값
          dp[1] = 1;
          dp[2] = 2;
          dp[3] = 4;
  
          // DP 계산
          /**
          * n   방법의 수
          * 1   1
          * 2   1+1, 2 => 2
          * 3   1+1+1, 1+2, 2+1 => 3
          * 4   1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 => 7 = 4 + 2 + 1
          * 5   1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+1+3, 1+2+1+1, 1+2+2, 1+3+1,2+1+1+1, 2+1+2, 2+2+1, 2+3, 3+1+1, 3+2 => 13 = 7 + 4 + 2
          */
          for (int i=4; i<=10; i++) {
              /**
              * dp[4] = dp[3] + dp[2] + dp[1]
              * dp[4] = 4 + 2 + 1
              * dp[4] = 7
              */
              dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
  //            System.out.println(dp[i]);
          }
  
          // 입력
          Scanner sc = new Scanner(System.in);
          int t = sc.nextInt();
          for (int i=0; i<t; i++) {
              int n = sc.nextInt();
              // 출력
              System.out.println(dp[n]);
          }
      }
  }

3. 문제 회고

• 🔍 시도

1,2,3을 이용해서 n을 만들어야 한다는 문제의 조건을 보고 DP 알고리즘을 떠올렸다.

• 🛠 해결 과정

점화식을 어떻게 세울지 고민하면서 여러 값을 직접 계산해보며 유도하였다.

• ✅ 잘한 점

문제를 읽고 적절한 알고리즘을 바로 떠올렸다는 점이 잘했다.

• ⚠ 개선할 점

점화식을 유도하는 과정에서 시간이 오래 걸렸다.

참조