공부 161일차: 백준 15664번 N과 M (10) 자바 java

15664 N과 M (10)

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

15664번: N과 M (10)

 

 

 

---

백준 15664번 문제 N과 M (10)

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/294

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

https://gimbalja.tistory.com/303

공부 160일차: 백준 15663번 N과 M (9) 자바 java

 

N과 M 10번째 문제는 이 문제들을 기반으로 한다

 

비내림차순은 말그대로 내림차순이 아닌 모든 것을 뜻하므로,

중복되는 수열이거나 오름차순인 수열임을 안다면 크게 어려울 것 없다

 

4번째 문제와 마찬가지로,

DFS메서드에 depth와 함께 start 매개변수를 두면 된다

왼쪽과 다른 점은 이와 관련된 것뿐이다

start 변수를 두어 현재 수 이전의 수, 즉 나보다 작은 수는 들어가지 않도록 한다(이전에 오름차순으로 정렬하므로)

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, m;
    static int[] arr, nums;
    static boolean[] visited;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
    
    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];
        nums = new int[n];
        visited = new boolean[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(nums);
        
        DFS(0, 0);
        bw.flush();
        bw.close();
    }
    
    static void DFS(int start, int depth) throws IOException {
        if(depth == m) {
            for(int val : arr) {
                bw.write(val+" ");
            }
            bw.newLine();
            return;
        }
        
        int before = 0;
        for(int i = start; i < n; i++) {
            if(visited[i]) {
                continue;
            }
            
            if(before != nums[i]){    
                visited[i] = true;
                arr[depth] = nums[i];
                before = nums[i];
                DFS(i, depth+1);
                visited[i] = false;
            }
        }
    }
    
 
}
 

 

계속 반복되는 문제 패턴

 

 

 

---