[백준 BOJ 15649번] N과 M (1)

출처 : https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

1. 문제

 

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

---

2. 입력

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

3 1

4 2

4 4

---

3. 출력

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

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

1
2
3

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

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

---

4. 풀이

전에 푼 N-Queens 문제와 비슷한 맥락으로 코드를 짰다. 다른 점이 있다면 N-Queens에서는 1차원 배열에 입력하는 것이 열번호이기에 시작점이 0이었지만 이 문제는 입력하는 내용이 1~N이기에 for문 작성 시 아주 미세한 차이만 주면 되었다.

---

5. 소스코드

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

class Main{

    public static int N;
    public static int M;
    public static int [] n_arr;

    public static void main(String []args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        n_arr = new int [M];
        possible_arr(0);
    }

    public static boolean promising(int i){
        for(int j=0; j<i; j++){
            if(n_arr[j] == n_arr[i]) return false;
        }
        return true;
    }

    public static void possible_arr(int i){
        if(i == M){
            for(int j=0; j<M; j++){
                System.out.print(n_arr[j]+" ");
                
            }
            System.out.println("");
            return;
        }

        for(int j=1; j<=N; j++){
            n_arr[i] = j;
            if(promising(i)) possible_arr(i+1);
        }
    }
}

---

6. 배운 것

정렬 가능한 경우의 배열을 출력을 진행하고서 끝마칠 때 return;을 해주어야 뒤로 돌아갈 수가 있다. 이점을 간과하지 말자.