알고리즘 풀이 - 백준 15656(N과 M(7), 완전탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조
백트래킹 관련 포스팅은 여기를 참조

관련 문제인 N과 M(1)은 여기를 참조
관련 문제인 N과 M(2)는 여기를 참조
관련 문제인 N과 M(3)은 여기를 참조
관련 문제인 N과 M(4)는 여기를 참조
관련 문제인 N과 M(5)는 여기를 참조
관련 문제인 N과 M(6)는 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

이 문제는 N과 M(3)과 동일하지만 N개의 자연수가 10,000이하의 임의의 서로 다른 숫자로 주어진 다는 것만 다르다.

 

2. 풀이

 

이 문제는 백트래킹 관련 문제이다.(백트래킹은 상단 링크 포스팅 참조)

이전의 관련 문제(상단 링크 참조)인 N과 M(5), N과 M(6)과의 차이는 같은 숫자를 여러 번 써도 된다는 것이다.

즉, 이전 처럼, 현재의 숫자가 이미 포함되었는지 아닌지를 알 필요가 없다. 다만, 그렇다보니 출력에 큰 시간이 소요될 수 있다.

 

실제로 이 문제는 N개의 숫자 중 M개를 고르지만 중복이 허용되기 때문에 시간복잡도가 $O(N^M)$이 되기 때문에 이전 문제에 대비 더 많은 시간이 소요된다.

 

따라서 StringBuilder 또는 BufferedWriter를 사용하여 출력하지 않고 단순히 System.out.print를 통해서 수행 시 시간 초과가 발생한다.

자세한 것은 코드로 알아보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

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

public class Main{
    static int n;
    static int m;
    static int[] nums;
    static int[] selected;
    static StringBuilder sb;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);
        nums = new int[n];
        selected = new int[m];
        
        line = br.readLine().split(" ");
        for(int i=0; i < n; i++){
            nums[i] = Integer.parseInt(line[i]);
        }
        
        // 숫자를 미리 정렬시킴
        Arrays.sort(nums);
        
        go(0);
        System.out.println(sb);
        br.close();
    }
    
    private static void go(int seq){
        if(seq == m){
            for(int i : selected){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        // 같은 숫자가 있는지, 이전 숫자의 크기가 몇인지 등을 체크하지 않고
        // 바로 다음 숫자로 넘어간다.
        for(int i=1; i <= n; i++){
            selected[seq] = nums[i-1];
            go(seq+1);
        }
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.