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

15665 N과 M (11)

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

15665번: N과 M (11)

 

 

 

---

백준 15665번 문제 N과 M (11)

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

 

https://gimbalja.tistory.com/303

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

 

11번째 문제는 9번째 문제와 유사하다

 

다른 조건은 모두 같고,

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

굵게 처리한 이 부분의 조건만 다르다

 

이 부분을 처리하기 위해서는, 방문했던 수를 true로 바꾸는 역할을 했던 visited[]를 없애고,

중복된 수열만 들어가지 않도록 하면 된다

 

이때 이용하는 것이 전에도 사용했던 before 변수다

이전에 들어갔던 수를 체크하여 같지 않을 때만 arr에 들어갈 수 있도록 한다

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, m;
    static int[] arr, nums;
    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];
        
        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;
        }
        
        int before = 0;
        for(int i = 0; i < n; i++) {
            if(before != nums[i]) {    // 이전에 들어갔던 수랑 다르면 == 중복이 아니면    
                arr[depth] = nums[i];
                before = nums[i];
                DFS(depth+1);
            }
        }
    }
 
}
 

계속 반복되는 문제 패턴

 

 

 

---