공부 157일차: 백준 15655번 N과 M (6) 자바 java

15655 N과 M (6)

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

15655번: N과 M (6)

 

 

 

 

---

백준 15655번 문제 N과 M (6)

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

 

N과 M 6번째 문제https://gimbalja.tistory.com/291

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

https://gimbalja.tistory.com/295

공부 156일차: 백준 15654번 N과 M (5) 자바 java

이 두 문제를 적절히 섞으면 되는 문제다

 

주어지는 숫자로만 이루어진 수열 중 오름차순인 것만 출력한다

 

 

 

https://gimbalja.tistory.com/294

공부 155일차: 백준 15652번 N과 M (4) 자바 java

아니면 이 문제처럼 start 정수를 입력받게 하는 것도 가능

 

 

 

 

---

정답 인정 코드

---

 

 

1)

 

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int n, m;
    static int[] arr;
    static int[] nums;    // 주어지는 수를 입력받기 위한 배열 생성
    static BufferedWriter bw;
    static boolean[] visited;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m];
        nums = new int[n];    
        visited = new boolean[10_001];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(nums);    // 사전순대로 출력하기 위해 오름차순 정렬
        
        DFS(0);
        bw.flush();
        bw.close();
    }
    
    static void DFS(int depth) throws IOException{
        if(depth == m) {
            for(int val : arr) {
                bw.write(val+" ");
            }
            bw.newLine();
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if(!visited[nums[i]]) {    // 이전 i 자리에 nums[i]를 넣어 입력 받은 숫자만 들어가도록
                visited[nums[i]] = true;
                arr[depth] = nums[i];
                DFS(depth+1);
                for(int j = i+1; j < n; j++) {
                    if(visited[nums[j]]) {        
                        visited[nums[j]] = false;
                    }
                }
            }
        }
    }
 
}
// 과정 

배열 추가해주고 기존 DFS의 i 자리에 그 배열만 넣으면 된다

 

 

 

---

유형이 다양해서 정답률도 높고, DFS에 대해 더 깊게 이해하게 되어 재미도 있다