[백준/JAVA] 12101번: 1, 2, 3 더하기 2

코테/백준

[백준/JAVA] 12101번: 1, 2, 3 더하기 2

imname1am 2023. 5. 29. 15:37

🔺 문제

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

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

www.acmicpc.net

🔺 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

import java.util.*;
import java.io.*;
 
public class Main {
    static int n, k;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        ArrayList<String>[] A = new ArrayList[n + 3];
        for(int i = 0 ; i < n + 3 ; i++) {
            A[i] = new ArrayList<>();
        }
        
        A[1].add("1");
        A[2].add("1+1");
        A[2].add("2");
        A[3].add("1+1+1");
        A[3].add("1+2");
        A[3].add("2+1");
        A[3].add("3");
        
        for(int i = 4 ; i <= n ; i++) {
            for(int j = 1 ; j <= 3; j++) {
                for(String s : A[i - j]) {
                    A[i].add(s + "+" + j);
                }
            }
        }
        
        if(A[n].size() < k) {
            System.out.println(-1);
        }
        else {
            Collections.sort(A[n]);    // 오름차순 정렬
            System.out.println(A[n].get(k - 1));
        }
    }
}
Colored by Color Scripter

cs