BJ S1 15650 N과M(2) - Java

[문제링크]

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

---

[문제]

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

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

---

[입력]

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

---

[출력]

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

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

---

[예제 입력 1]

3 1

---

[예제 출력 1]

1
2
3

 

---

[예제 입력 2]

4 2

---

[예제 출력 2]

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

---

[예제 입력 3]

4 4

---

[예제 출력 3]

1 2 3 4

---

[설명]

항상 백트래킹을 공부하면 N과M을 풀어보는 것 같다. 그것도 N과M 10번까지 하루에 다 풀었던 것 같다.한번에 하면 쉽게 금방 풀지만, 다음에 백트래킹 관련해서 풀 문제가 별로 없기 때문에 이번에는 하루에 한문제씩만 풀자고 다짐해봤다.

 

N과M(1)과는 다른 점은 앞의 수가 뒤의 수보다 작아야 한다는 점이다.때문에  if(arr[depth-1]) 구문을 통해 해당 로직을 구현하였다.

 

 

백준 알고리즘 15650번 JAVA풀이

 

import java.util.*;

public class BJ15650 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] arr = new int[M];
        boolean[] visited = new boolean[N+1];

        backtracking(arr, visited, 0);
    }

    public static void backtracking(int[] arr, boolean[] visited, int depth) {
        if(depth == arr.length){
            for(int i=0;i<depth;i++){
                System.out.print(arr[i]+" ");
            }
            System.out.println();
            return;
        }

        for(int i=1;i<visited.length;i++){
            if(!visited[i]){
                if(depth==0){
                    arr[depth]=i;
                    visited[i]=true;
                    backtracking(arr, visited, depth+1);
                    visited[i]=false;
                }else{
                    if(arr[depth-1]<i){
                        arr[depth]=i;
                        visited[i]=true;
                        backtracking(arr, visited, depth+1);
                        visited[i]=false;
                    }
                }
            }
        }
    }
}

 

 

 

궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.