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

 

관련글

 

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

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

이전 문제인 N과 M(2)와 비슷한데, 중복이 허용되며, 비 내림차순이라는 것이 추가되었다.

 

 

2. 풀이

 

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

 

 

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

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

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

 

 

3. 코드

 

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

 

import java.io.*;

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

 

 

4. 다른 방법으로 풀어보기

 

이 문제로 지난 N과 M(2)와 같이 다른 방법으로 풀어볼 수 있다. 이 문제는 N개의 숫자 중 중복을 허용하여 M개를 선택해야 한다.
(해당 포스팅을 보고 오면 더 이해가 쉬울 것이다. 링크는 여기)

 

이 때, 비 내림차순이라는 말이 없이 전체 N개 중 M개를 지속 선택해야 하는 경우 총 시간복잡도가 $O(N^M)$
오름차순이라면 전체 N개 중 M개를 선택하되 다음 선택할 수 있는 숫자가 제한되어 시간복잡도가 $O(N!)$이 된다.

그러니 비 내림차순으로 구하는 이 문제는 그 사이의 어느 정도의 시간복잡도를 갖게 된다. 하지만 이를 더 낮출 수 있다!

 

N과 M(2)의 포스팅에서는 오름차순이기 때문에 각 숫자를 선택하거나 선택하지 않거나의 둘 중 하나로 나누어 재귀로 해결할 수 있고 이를 통해 시간복잡도를 $O(2^N)$으로 낮출 수 있었다.

해당 문제에서 이번에는 비 내림차순이기 때문에 동일한 숫자가 한 번 더 추가될 수 있다는 것만 바뀐 것이다.

아래의 코드에서 이전에는 go(seq+1, idx+1)로 현재 idx 숫자가 선택된 경우에는 바로 다음 숫자를 선택하도록 하였지만, 이번에는 go(seq+1, idx)로 한 번 더 이번 숫자가 선택될 수 있는 경우를 체크하면 된다.

 

코드를 통해 더 직관적으로 이해해보자.

 

import java.io.*;

public class Main{
    static int n;
    static int m;
    static StringBuilder sb;
    static int[] num; // 수열 저장하는 배열
    
    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]);
        
        num = new int[m];
        
        go(0, 1);
        
        System.out.println(sb);
        br.close();
    }
    
    
    // seq는 몇 개의 숫자가 선택되었는지를 알아내는 부분
    // idx는 현재 몇 번째의 숫자를 선택 / 미선택할 것인지를 채택하는 부분
    private static void go(int seq, int idx){
        if(seq == m){
            for(int i : num){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        // 아래에서 반복문이 사라진 것을 알 수 있음!
        // 이를 통해 재귀만 사용하여 해결하여 더 빠른 시간복잡도를 유지
        
        // 만약 계속 재귀를 통해 넘어가면 언젠간 n을 넘어가게 되니, 그 이후에는 바로 반환시킴
        if(idx > n) return; 
        
        // 현재 숫자를 선택하는 경우의 재귀 방식
        // 이후 다음 선택할 숫자로 넘어가는데, 현재 숫자를 또 선택하는 것도 가능!
        num[seq] = idx;
        go(seq+1, idx);
            
        // 현재 숫자를 선택하지 않는 경우의 재귀 방식
        // 현재 seq번째의 선택될 숫자를 다음 숫자부터 판단함!
        num[seq] = 0;
        go(seq, idx+1);
    }
}

 

 

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