Q 12101 1,2,3 더하기 2

💡 문제 요약 및 분석

정수 N 을 1,2,3 의 합으로 나타내는 방법을 사전 순서로 나열했을 때, K번째로 오는 조합을 구하자.

💡 알고리즘 설계

✅ 백트래킹 조건 : 다음에 더하는 수는 1, 2, 3 으로 정해져 있다. for문으로 모든 경우의 수를 계산하면 된다.

1. 입력

   • 표준입력 : int n, int k
   • List<> memo = new ArrayList<>();

2. 연산

   • backTracking(int num, int cal, String result); cal 은 계산을 위한 변수, result 는 정답 문자열을 저장한다.
   • cal == n 일 때 memo에 저장한다.
   • cal > n 일 때 재귀함수를 종료한다.

3. 출력

   • memo.get(k - 1) 출력한다. 만약 k <= memo.size() 라면 -1 을 출력한다.

💡 코드

import java.util.ArrayList;
import java.util.List;

public class Main {

    static int n;
    static int k;
    static List<String> memo;

    static int read() throws Exception {
        int c = 0, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        n = read();
        k = read();
        memo = new ArrayList<>();

        for (int i = 1; i <= 3; i++) {
            backTracking(1, i, i + "");
        }

        if (k <= memo.size()) {
            System.out.println(memo.get(k - 1));
        } else {
            System.out.println(-1);
        }
    }

    static void backTracking(int num, int cal, String result) {
        if (cal > n) return;

        if (cal == n) {
            memo.add(result);
            return;
        }

        for (int i = 1; i <= 3; i++) {
            backTracking(i, cal + i, result + "+" + i);
        }
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(3^n)	O(n)