[백준] 15666 : N과 M (12) (백트래킹) - JAVA

solved ac (실버2)

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

 

# 문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

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

 

# 예제

입력 : 

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

4 2
9 7 9 1

 

출력 : 

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

1 1
1 7
1 9
7 7
7 9
9 9

 

# 필요개념

 

이 문제는 N과 M(9)와 달리, 같은 수를 중복으로 선택하는 게 가능하고, 한 수열 안에서도 오름차순 형태여야 한다. 그래서 나는 입력을 받은 후, 중복제거를 하고 오름차순 정렬을 했다. (어짜피 중복선택이 가능하므로 input배열의 중복을 제거해도 상관없다는 판단이었다. 오히려 잘만 하면 N의 크기를 크게 줄일 수 있다.)

 

M크기의 배열이 완성되면 리스트에 넣어두고, 이를 비교할 때 사용한다.

리스트의 가장 최근 배열을 가지고 비교하는데, 과정은 아래 예를 들어 설명하겠다. 참고로, 최근배열을 가지고 비교하므로 모든 값이 0인 배열을 가장 처음에 넣어주어 비교대상이 없어지는 것을 방지한다.

 

 

위와 같은 과정을 반복하면, 따로 정렬을 할 필요도 없어진다.

 

 

# Code

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

public class Main {
    static int[] input;
    static List<int[]> lst = new ArrayList<>();
    static int[] output;
    static int N;
    static int M;

    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());
        M = Integer.parseInt(st.nextToken());

        input = new int[N];
        output = new int[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0 ; i < N ; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }

        // 리스트의 가장 최근 배열을 비교할 떄 사용할 것이므로, {0, 0 ...} 배열을 디폴트로 넣어두었다. (OUTOFINDEX 방지)
        lst.add(new int[M]);

        input = Arrays.stream(input).distinct().sorted().toArray();
        N = input.length;
        dfs(0);

    }

    private static void dfs(int cnt) {
        if (cnt == M) {
            lst.add(output);
            for (int i = 0 ; i < M ; i++) {
                System.out.print(output[i] + " ");
            }
            System.out.println();
        } else if (cnt == 0) {
            for (int i = 0 ; i < N ; i++) {
                output[0] = input[i];
                dfs(1);
            }
        } else {
            for (int i = 0 ; i < N ; i++) {
                if (output[cnt - 1] <= input[i]) {
                    if (lst.get(lst.size() - 1)[cnt] == input[i] && output[cnt - 1] != input[i]) continue;
                    else {
                        output[cnt] = input[i];
                        dfs(cnt + 1);
                    }
                }
            }
        }
    }
}

 

# 결과