공부 163일차: 백준 15666번 N과 M (12) 자바 java

15666 N과 M (12)

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

15666번: N과 M (12)

 

 

 

---

백준 15666번 문제 N과 M (12)

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

 

https://gimbalja.tistory.com/305

공부 162일차: 백준 15665번 N과 M (11) 자바 java

 

https://gimbalja.tistory.com/304

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

12번째 문제는 11번째 문제에서 조건이 하나 추가되었다

 

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

결국 10번, 11번 문제를 결합하면 쉽게 풀리는 문제다

public 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(before != nums[i]) {    // 중복처리
            visited[i] = true;    // 비내림차순처리 1
            arr[depth] = nums[i];
            before = nums[i];
            DFS(i, depth+1);
            visited[i] = false;    // 비내림차순처리 2
        }
    }
}

before 변수로 중복 체크하고

visited[]로 비내림차순으로 들어올 수 있도록 한다

 

 

 

---

정답 인정 코드

---

 

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();
    }
 
    public 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(before != nums[i]) {    // 중복처리
                visited[i] = true;    // 비내림차순처리 1
                arr[depth] = nums[i];
                before = nums[i];
                DFS(i, depth+1);
                visited[i] = false;    // 비내림차순처리 2
            }
        }
    }
}
 

 

계속 반복되는 문제 패턴

 

 

 

---

N과 M 마지막 문제까지 다 풀었다

DFS에 친숙해진 것 같아 기쁘다