[백준 알고리즘] 15650번 자바(Java) N과 M(2)

조건

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

 

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

풀이

문제를 보면 백트래킹 문제인것을 알 수 있다.
시간복잡도를 계산하자면 N까지의 수를 M의 값만큼 반복해서 구해야 하기때문에  O(N^M) 이 된다.
예시를 들자면 1~4까지의 수로 3길이의 수열을 만든다고 생각하면 4x4x4가 된다.

이 문제의 최대 N과 M은 8이고 그러면 8^8승 약 1600만이 되므로 시간상에서는 문제가 없다.

문제 내용으로 넘어가서 dfs방식으로 해야하는데 방문체크를 해줘야한다. 

이유는 중복되는 수열을 여러번 출력하면 안된다. 이말의 예시를 들자면
N = 4,   M= 2일때
1 2 수열이 나오면 2 1 수열은 중복되므로 출력되면 안된다. 그러기 위해서 

dfs 안에 반복문에서 i = 1부터가 아니라 i=num부터로 설정했다.  그렇게되면
1 2 나온이후에 2로 시작하는 dfs에서는 2 1로 갈 수 없다. 2 3부터 시작인거다.
이런 방법으로 아래 코드를 짰다.

 

예제 입력 예시

4 2

 

예제 출력 예시

1 2
1 3
1 4
2 3
2 4
3 4

 

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//15650번 N과 M(2)

public class Main {
    static StringBuilder sb;
    static int M;
    static int N;
    static boolean[] visited;  //방문한 자연수 체크

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        visited = new boolean[M+1];
        sb = new StringBuilder();
        for (int i = 1; i <=M; i++) {
            visited[i] = true;
            dfs(i, N, "");
        }
        System.out.println(sb);
    }

    static void dfs(int num, int cnt, String str){
        str = str+num+" ";
        cnt--;
        if(cnt != 0){
            //기존 N과 M과다른점은 i=1부터가 아니라 i=num부터 해서 중복안됨 + 전에 나온 수열 중복x
            for (int i = num; i <=M; i++) {
                if(!visited[i]){
                    visited[i] = true;    //dfs에 들어가기전 방문체크
                    dfs(i, cnt, str);
                    visited[i] = false;    //dfs에 들어가고 난후 방문해제
                }
            }
        }
        else{
            sb.append(str).append("\n");
        }
    }
}

 

 

 

 

문제 출처

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

15650번: N과 M (2)