[백준] 12101. 1, 2, 3 더하기

정수 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
2. 1+1+2
3. 1+2+1
4. 1+3
5. 2+1+1
6. 2+2
7. 3+1

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

---

입력

첫째 줄에 정수 n과 k가 주어진다. n은 양수이며 11보다 작고, k는 231-1보다 작거나 같은 자연수이다.

출력

n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다.

---

예제 입력 3

4 7

예제 출력 3 

3+1

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int n;
    public static int k;
    public static int idx = 0;
    
    public static void main(String[] args) throws Exception {
        int[] arr = {0, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504};
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        if(k > arr[n]) {
            System.out.println("-1");
        } else {
            resFunc(1, "1");
            resFunc(2, "2");
            resFunc(3, "3");
        }
    }
    
    public static void resFunc(int res, String exp) {
        if(res > n) {
            return;
        }
        if(res == n) {
            idx++;
            if(idx == k) {
                System.out.println(exp);
            }
            return;
        }
        if(res + 1 <= n) {
            resFunc((res + 1), exp + "+1");   
        }
        if(res + 2 <= n) {
            resFunc((res + 2), exp + "+2");   
        }
        if(res + 3 <= n) {
            resFunc((res + 3), exp + "+3");   
        }
    }
}

arr에 n의 경우의수 숫자를 규칙을 찾아 저장해놓고

 

k번째 식이 경우의 수를 넘어가는 수가 나오면 못찾는거니 넘어간다.

1, 2, 3의 합을 구성하니 1, 2, 3 각각의 수에 다시 1, 2, 3씩 실제 숫자도 더하고 문자열도 append하면서 n에 도착하면 해당 문자열을 출력한다.