백준 [15666] N과 M (12)

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

15666번: N과 M (12)

 

풀이

같은 수를 여러번 고르는 건 되지만 중복되는 수열을 여러번 출력하는 것은 안된다.

또한 비 내림차순으로 정렬되어야 한다.

 

출력할 정답을 담을 정답 배열을 하나 선언 (크기는 M만큼)

 

비내림차순으로 뽑기 위해서 정렬을 해준다음 진행한다.

같은 수를 여러 번 고르는 것을 고려하면 방문 배열을 사용하지 않고 from을 사용해서 dfs 탐색을 진행하면

중복되는 수열이 포함되는 비내림차순 수열을 뽑을 수 있는 코드이다.

static void dfs(int from, int depth) {
    if (depth == M) {
        for (int i = 0; i < M; i++) {
            sb.append(ans[i] + " ");
        }
        sb.append("\n");
        return;
    }

    for (int i = from; i < N; i++) {
            ans[depth] = a[i];
            dfs(i, depth + 1);
    }
}

 

결과

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

 

같은 수 여러 개가 입력으로 들어와서 중복되는 수열이 발생한다.

이를 제거하기 위해 before 변수를 활용하여 이전에 골랐던 수와 같은 수이면 고르지 않도록 처리

int before = 0;
for (int i = from; i < N; i++) {
    if (before != a[i]) {
        ans[depth] = a[i];
        before = a[i];
        dfs(i, depth + 1);
    }
}

 

 

정답 코드

package com.baekjoon.p15666;

import java.util.*;

public class Main {
    static int N, M;
    static int[] a;
    static int[] ans;

    static StringBuilder sb = new StringBuilder();

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

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

        a = new int[N];
        ans = new int[M];

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

        Arrays.sort(a);

        dfs(0, 0);
        System.out.println(sb);
        sc.close();
    }

    static void dfs(int from, int depth) {
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                sb.append(ans[i] + " ");
            }
            sb.append("\n");
            return;
        }

        int before = 0;
        for (int i = from; i < N; i++) {
            if (before != a[i]) {
                ans[depth] = a[i];
                before = a[i];
                dfs(i, depth + 1);
            }
        }
    }
}