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

1. 문제

12101번: 1, 2, 3 더하기 2

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

이를 사전순으로 정렬하면 다음과 같이 된다.

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

정수 n과 k가 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하는 프로그램을 작성하시오.

---

2. 풀이

Main

dp를 미리 구해둔다. dp[0]을 1로 한 이유는 마지막 숫자를 체크하기 위해서다. 뒤에서 설명한다.

만약 K가 dp[N]보다 크다면 -1을 출력하고 끝낸다.

재귀함수 find를 호출하고 sb를 출력한다. 이때, 마지막 글자(+)는 지우고 출력한다.

static StringBuilder sb = new StringBuilder();
static int[] dp = new int[11];
public static void main(String[] args) throws IOException {
   dp[0] = 1; 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];
   StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());
   int N = Integer.parseInt(st.nextToken());
   int K = Integer.parseInt(st.nextToken());

   if(dp[N]<K){
      System.out.println(-1);
      return;
   }

   find(N,K);
   sb.setLength(sb.length()-1);
   System.out.println(sb);
}

 

Find

1부터 3까지 반복문으로 n-i를 탐색한다.

만약 n-i가 0보다 작다면 끝낸다.

k가 dp[n-i]보다 작거나 같다면 i + find(n-i, k)를 다시 찾아야 한다.

k가 dp[n-i]보다 크다면 식은 "i + 새로운 식"형태가 아닌 것이다. k에서 dp[n-i]값만큼 빼고 다음 탐색을 진행한다.

public static void find(int n, int k){
   for(int i=1;i<=3;i++){
      if(n-i<0) break;
      if(dp[n-i] >= k){
         sb.append(i).append('+');
         find(n-i,k);
         break;
      }
      k-=dp[n-i];
   }
}

 

전체 코드

import java.io.*;
import java.util.*;

public class BOJ_12101_123더하기2 {
   static StringBuilder sb = new StringBuilder();
   static int[] dp = new int[11];
   public static void main(String[] args) throws IOException {
      dp[0] = 1; 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];
      StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());
      int N = Integer.parseInt(st.nextToken());
      int K = Integer.parseInt(st.nextToken());

      if(dp[N]<K){
         System.out.println(-1);
         return;
      }

      find(N,K);
      sb.setLength(sb.length()-1);
      System.out.println(sb);
   }
   public static void find(int n, int k){
      for(int i=1;i<=3;i++){
         if(n-i<0) break;
         if(dp[n-i] >= k){
            sb.append(i).append('+');
            find(n-i,k);
            break;
         }
         k-=dp[n-i];
      }
   }
}

---

3. 결과