백준 [15664] N과 M (10)

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

 

문제의 조건

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
• 추가 조건으로 중복되는 수열을 여러 번 출력하면 안된다는 조건이 들어가 있었다.

 

풀이

 

before 변수를 지정하여 이전에 골랐던 수와 동일한 수를 골랐는지 체크해준다.

 

예제 입력 2의 케이스를 보면

4 2
9 7 9 1

 

출력

1 7
1 9
7 9
9 9

 

7의 경우 7 1 을 건너뛰고 7 9로 가기 때문에 매개 변수로 지정한 from을 통해 탐색을 시작할 범위를 지정해주었다.

 

그리고 중복을 제거해주기 위해 방문 배열 v를 선언해주었다.

 

워낙 시리즈가 많은 문제라 시리즈를 차례로 풀어왔으면 엄청 많이 헷갈리진 않았을건데 시간이 지나고 다시 보니 조건을 주는 부분이 많이 헷갈렸다.

 

전체 코드

package com.baekjoon.p15664;

import java.util.*;

public class Main {
    static int N, M;
    static int[] arr, res;
    static boolean[] v;

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

        N = sc.nextInt();
        M = sc.nextInt();

        arr = new int[N];
        v = new boolean[N];

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);
        res = new int[M];
        dfs(0, 0);
        sc.close();
    }

    static void dfs(int from, int depth) {
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                System.out.print(res[i] + " ");
            }
            System.out.println();
            return;
        }

        int before = -1;
        for (int i = from; i < N; i++) { // from 부터 시작해서 뽑음
            int now = arr[i];
            if (before == now || v[i]) { // 이전에 뽑았던 수이거나 한번 고른 수열이면 중복 수열이 되므로 넘어감
                continue;
            } else {
                v[i] = true;
                before = now; // 현재 수열을 이전에 뽑았던 수로 갱신
                res[depth] = arr[i];
                dfs(i + 1, depth + 1);
                v[i] = false;
            }
        }
    }
}

 

그리고 dfs() 재귀를 탈 때 dfs(i+1, depth+1)이 아닌 dfs(from+1, depth+1)으로 해주어서 틀렸었다. 이렇게 하면 시작 범위가 잘 못되어 오답으로 처리 되었다.