[BOJ] 9095 1, 2, 3더하기 - JAVA

1. 문제

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

9095번: 1, 2, 3 더하기

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

이 문제 설명이 좀 이상하다. n을 1,2,3의 합이 아니라 1,2,3 조합으로 설명해야 차라리 명확할 것 같다. 문제만 보면 2는 1+1만 되고 2는 안될 것 같은데 2도 된다.

1 --> 1

2 --> 1+1, 2

3 --> 1+1+1, 2+1, 1+2, 3

4 --> 1+1+1+1, 1+3, 1+1+2, 1+2+1, 2+2, 2+1+1, 3+1

n --> 1+(n-1), 2+(n-2), 3+(n-3)

---

2. 풀이

규칙

• n --> 1+(n-1), 2+(n-2), 3+(n-3) 세 경우로 나눠서 생각하면 된다.
• 따라서 f(n)==>f(n-1)+f(n-2)+f(n-3) 이다.
• 아주 간단한 한 줄이지만 생각하는 데 정말 오래걸렸다. DP는 푸는 것보다 규칙 찾는게 제일 힘들다. 

코드

import java.io.*;

public class BOJ_9095_123더하기 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringBuilder sb = new StringBuilder();
      int T = Integer.parseInt(in.readLine());

      int[] nums = new int[12];
      nums[1] = 1;
      nums[2] = 2;
      nums[3] = 4;

      while(--T>=0){
         int N = Integer.parseInt(in.readLine());

         if(nums[N]!=0) {
            sb.append(nums[N]).append("\n");
            continue;
         }

         for(int i=4;i<=N;i++){
            if(nums[i]!=0) continue;
            nums[i] = nums[i-1]+nums[i-2]+nums[i-3];
         }

         sb.append(nums[N]).append("\n");
      }
      System.out.print(sb);
   }
}

---

3. 결과

왜 틀렸지??? 했는데 문제를 잘못 봤다. 이걸 잘못봤다고 해야하나.. 아무튼 2는 {1+1, 2}다.