공부 153일차: 백준 15650번 N과 M (2) 자바 java

15650 N과 M (2)

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

15650번: N과 M (2)

 

 

 

---

백준 15650번 문제 N과 M (2)

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/290

공부 152일차: 백준 1748번 N과 M (1) 자바 java

N과 M(1) 문제에서 오름차순 조건이 추가된 문제다

 

이를 위해서는 다시 방문하기 위해서 줬던 false 부여 방식을 바꿔야 한다

현재 들어온 숫자의 visited[]는 그대로 true로 두고 그 이후의 숫자들을 다시 false로 바꿔주면 오름차순으로 들어올 수 있다

코드로 보면 쉽게 이해할 수 있을 것이다

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n;
    static int m;
    static int[] arr;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();
    
    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());
        
        arr = new int[m];
        visited = new boolean[n];
        DFS(0);
        System.out.println(sb);
 
    }
    
    static void DFS(int depth) {
        if(depth == m) {
            for(int num : arr) {
                sb.append(num).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                arr[depth] = i+1;
                DFS(depth+1);
                for(int j = i+1; j < n; j++) {
                    // visited는 작은 수부터 시작 -> visited[i+1], visited[i+2], ... 에는 무조건 앞보다 큰 숫자들이 들어으므로 자동으로 오름차순
                    visited[j] = false;
                }
            }
        }
    }
 
}
 

 

 

 

 

---

dfs가 되게 어렵게 느껴진다 그래도 n과 m(1)부터 다 하면서 익숙해지길 바란다