[JAVA] 백준 (실버3) 15650번 N과 M (2)

링크

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

---

문제 설명

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

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

---

입력 예제

4 2

---

출력 예제

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

---

정답 코드

DFS(깊이우선탐색)을 사용한다.
이전 N과 M (1) 문제와 유사하다.
대신 배열이 오름차순일 때만 출력하면 된다.
매번 1부터 N까지 방문할 필요가 없으므로
start 변수를 추가하여
for문의 시작점을 갱신해준다.

위 예제를 가지고 순서를 적어보면 다음과 같다.

• dfs(깊이, 시작점)
• dfs(0, 1)
  • i = 1
    • arr[0] = 1
    • dfs(1, 2)
      • i = 2
        • arr[1] = 2
        • dfs(2, 3), {1, 2} 출력
      • i = 3
        • arr[1] = 3
        • dfs(2, 4), {1, 3} 출력
      • i = 4
        • arr[1] = 4
        • dfs(2, 5), {1, 4} 출력
  • i = 2
    • arr[0] = 2
      ...
      

import java.io.FileInputStream;
import java.io.IOException;
import java.util.Scanner;

public class Main {

    static int N;
    static int M;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();   //1 ~ n
        M = sc.nextInt();   //m개 선택
        int start = 1;
        int depth = 0;

        arr = new int[M];
        dfs(depth, start);
        System.out.println(sb);
    }
	//dfs 메서드
    static void dfs(int depth, int start) {
		//깊이가 M일 때 sb에 추가후 return
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }
		//start를 기준으로 반복한다
        for (int i = start; i <= N; i++) {
            arr[depth] = i;
            dfs(depth + 1, i + 1);
        }
    }
}

---

정리

처음에는 이전 문제와 거의 같아서
저번 코드에다 출력되기 전 정렬된 배열과 비교한 뒤
같을 시에만 sb에 추가되도록 하였으나
시작점을 정해서 반복해두면 굳이 그럴 필요가 없었다.

//처음 작성한 코드
//원본 배열과 정렬된 배열을 비교하였다
if (depth == M) {
	int[] sorted = arr.clone();
    Arrays.sort(sorted);
    if (Arrays.equals(arr, sorted)) {
    	for (int val : arr) {
        	sb.append(val).append(" ");
        }
        sb.append("\n");
    }
    return;
}