BOJ15652 N과 M (4)

https://www.acmicpc.net/problem/15652 (opens new window)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구한다.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

고려해야 할 점

• 1부터 N까지 자연수 중에서 M개를 골라야 한다.
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이다.

같은 수를 여러 번 골라도 된다.

수열에 중복된 숫자를 허용한다. 즉 방문 여부를 가지고 있지 않아도 된다.

고른 수열은 비내림차순이다.

A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK을 만족하면 비내림차순이다. 즉 방금 탐색한 자신을 포함하여 다시 탐색을 진행한다. 이것을 구현하기 위해 start라는 변수를 추가적으로 사용한다.

제출 코드

아래는 최종 제출 코드이다.

public class BOJ15652 {
    private static int n;
    private static int m;
    private static List<String> results;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();

        results = new ArrayList<>();

        backtracking(0, 1, new int[m]);

        results.forEach(System.out::println);
    }

    private static void backtracking(int depth, int start, int[] values) {
        if (depth == m) {
            String result = Arrays.stream(values)
                .mapToObj(String::valueOf)
                .collect(joining(" "));
            results.add(result);
            return;
        }

        for (int i = start; i <= n; i++) {
            values[depth] = i;
            backtracking(depth + 1, i, values);
        }
    }
}

#BOJ #백트래킹