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

 

관련글

 

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

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

이 문제는 이전 N과 M(4)와 동일한데, 1~N개의 자연수가 아닌 10,000 이하의 임의의 서로 다른 N개의 자연수가 주어진다는 것이 다르다.

 

 

2. 풀이

 

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

 

이전 N과 M(4)와 풀이 방법은 동일하므로 아래의 내용을 참고하고, 코드를 보자

 

---

N, M이 주어질 때, M개의 수를 중복 허용하에 수를 고르되 비 내림차순으로 출력하고 전체 수열은 사전 순으로 고르므로 아래와 같이 우선 파악하자.

① 숫자를 M개 골랐다면 그 숫자를 출력해야 한다.
② 이미 고른 숫자를 다시 선택할 수 있지만 더 작은 숫자는 선택할 수 없다.
③ 사전 순으로 출력해야 하므로 1부터 N까지의 반복문을 사용하는 것이 좋다.

코드를 통해 확인하는 것이 더욱 직관적이므로 코드를 확인하자.

 

 

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, 1);
        
        System.out.println(sb);
        br.close();
    }
    
    // start값은 해당 숫자부터 반복문을 시작하도록 하여 이전의 더 작은 숫자를
    // 추가할 필요가 없도록 만든다.
    private static void go(int seq, int start){
        if(seq == m){
            for(int i : selected){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        // start부터 파악 시작
        for(int i=start; i <= n; i++){
            selected[seq] = nums[i-1];
            // 현재 i값이 또 선택되어도 되기 때문에, i를 start로 그대로 전달
            go(seq+1, i);
        }
    }
}

 

 

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