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

👀 문제

12101번: 1, 2, 3 더하기 2 ✨ 실버 1

정수 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번째로 오는 식을 구하는 프로그램을 작성하시오.

🔑 키포인트

브루트포스 알고리즘 백트래킹

✍️ 코드

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

public class BOJ12101 {
    static ArrayList<ArrayList<Integer>> com;
    static ArrayList<Integer> c;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        com = new ArrayList<ArrayList<Integer>>();
        c = new ArrayList<Integer>();
        
        back(n, k, 0);    
        
        if (com.size() < k) {
            System.out.println(-1);
        } else {
            int size = com.get(k-1).size();
            c = com.get(k-1);
            
            for (int i = 0; i < size-1; i++) {
                System.out.print(c.get(i) + "+");
            }
            System.out.print(c.get(size-1));
        }
        
    }
    
    @SuppressWarnings("unchecked")
    public static void back(int n, int k, int hap) {
        
        if (hap == n) {        
            com.add((ArrayList<Integer>)c.clone());
            return;
        }
        if (hap > n) {
            return;
        }

        for (int i = 1; i <= 3; i++) {
            c.add(i);
            back(n, k, hap+i);
            c.remove(c.size()-1);
        }
    }
}