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

🔺 문제

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

 

 

🔺 코드

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));
        }
    }
}

✅ 해결 아이디어
✔ DP
- ArrayList<String> 배열을 만들어 사용

 

 

---

🔺 다른 풀이들

- 백트래킹으로 푸셨다.

 

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

https://www.acmicpc.net/source/18547005

https://www.acmicpc.net/source/49863149

https://www.acmicpc.net/source/47833613

---

💬 느낀 점

나에게는 너무 어려운 다이나믹 프로그래밍...

모르겠어서 다른 분 풀이 보고 제출했다..ㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔

[알고리즘] 백준 12101 1, 2, 3 더하기 (2) Java