백준 12101 1, 2, 3 더하기 2 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/12101

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

1을 나타내는 식의 사전순 정렬
1

2를 나타내는 식의 사전순 정렬
1+1
2

3을 나타내는 식의 사전순 정렬
1+1+1
1+2
2+1
3

4를 나타내는 식의 사전순 정렬
1+1+1+1
1+1+2
1+2+1
1+3
2+1+1
2+2
3+1

다이나믹 프로그래밍 문제 풀이는 보통,
이전 단계에서부터 생각을 하면 된다.
이 문제는 1, 2, 3의 합으로 어떤 수를 나타내야 하는 문제이므로,

i >= 4일때
D(i) = D(i-1), D(i-2), D(i-3) 으로 구성된다.

예를 들어 위의 4를 나타내는 식의 사전순 정렬을 보면,
1로 시작하는 첫 네개의 식은 D(3) 에서 앞에 1만 붙이고,
2로 시작하는 두개의 식은 D(2) 에서 앞에 2만 붙이고,
3으로 시작하는 마지막 하나의 식은 D(1) 에서 앞에 3만 붙여서 온것이다.

여기까지 이해 되었으면 이제
마찬가지로 5를 나타내는 식의 사전순 정렬을 생각하면,
D(4) 의 식에서 앞에 1을 붙이면 D(5)
D(3) 의 식에서 앞에 2를 붙이면 D(5)
D(2) 의 식에서 앞에 3을 붙이면 D(5) 이다.
(D(1) 의 식에서 앞에 4를 붙이면 D(5)이긴 하지만, 4는 사용할 수 없다.)

해당 설명에 대한 코드는다음과 같다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        ArrayList<String>[] answer = new ArrayList[11];

        for(int i = 0 ; i <= 10 ; i++) {
            answer[i] = new ArrayList<String>();
        }

        answer[1].add("1");

        answer[2].add("1+1");
        answer[2].add("2");

        answer[3].add("1+1+1");
        answer[3].add("1+2");
        answer[3].add("2+1");
        answer[3].add("3");

        for(int i = 4 ; i <= 10 ; i++) {
            for(int j = 1 ; j <= 3 ; j++) {
                for(String s : answer[i-j]) {
                    answer[i].add(j + "+" + s);
                }
            }
        }

        if(answer[n].size() >= k) {
            bw.write(answer[n].get(k-1));
        }
        else{
            bw.write(String.valueOf(-1));
        }

        bw.flush();
        bw.close();


    }

}