공부 158일차: 백준 15656번 N과 M (7) 자바 java

15656 N과 M (7)

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

15656번: N과 M (7)

 

 

 

 

---

백준 15656번 문제 N과 M (7)

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/293

공부 154일차: 백준 15651번 N과 M (3) 자바 java

https://gimbalja.tistory.com/295

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

N과 M 7번째 문제는

위의 두 문제를 합친 거라고 생각하면 된다

 

주어진 숫자들로 수열을 이루는데, 그 조건이

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

위와 같다

 

따라서 visited[] 수열을 만들지 않고 노드에 있는 모든 숫자를 지나가게 하면 된다

호출 전 메인 메서드에서 오름차순 정렬을 해서 DFS 메서드 안에서는 따로 정렬 처리를 하지 않았다

 

for(int i = 0; i < n; i++) {            
    arr[depth] = nums[i];
    DFS(depth+1);    // 재귀로 호출하여 다음 깊이의 노드 탐색
}

 

결국 N과 M(3)에서 i가 nums[i]가 되는 것 뿐이다

 

 

 

 

 

---

정답 인정 코드

---

 

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.append(val+" ");
            }
            bw.newLine();    // == System.out.println();
            return;
        }
        
        for(int i = 0; i < n; i++) {            
            arr[depth] = nums[i];
            DFS(depth+1);    // 재귀로 호출하여 다음 깊이의 노드 탐색
        }
    }
 
}

 

과정에서 설명한 그대로다

 

 

 

---