백준 - 12101 - 1, 2, 3 더하기 2

https://www.acmicpc.net/problem/12101

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

 

import java.util.Scanner;

/**
 * 12101
 */
public class 일이삼더하기2 {
    private static int k;
    private static int count;
    private static String result = null;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");
        int targetNumber = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);
        backtracking(targetNumber, 0, new StringBuilder());
        if (result == null) {
            System.out.println(-1);
        } else {
            System.out.println(result);
        }
    }

    private static void backtracking(int targetNumber, int sum, StringBuilder mathExpression) {
        if (sum == targetNumber) {
            count++;
            if (count == k) {
                result = mathExpression.substring(0, mathExpression.length() - 1);
            }
        } else if (sum > targetNumber) {
            return;
        }

        for (int i = 1; i <= 3; i++) {
            mathExpression.append(i+"+");
            backtracking(targetNumber, sum + i, mathExpression);
            mathExpression.delete(mathExpression.length() - 2, mathExpression.length());
        }
    }
}

알고리즘

백트래킹을 이용하여 1,2,3으로 특정 숫자를 만들기 위한 조합을 구현하였습니다.

순서가 사전순으로 정렬이 되어야하는데, 따로 정렬을 해줄 필요는 없습니다. 왜냐하면 이미 for문에서 1,2,3 순으로 완전탐색을 하고 있기 때문이에요, 그래서 몇 번째 수식인지만 체크해주면 됩니다^.^