[백준/JAVA] 15655번: N과 M (6)

🔺 문제

15655번: N과 M (6)

 

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[] A, result;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();
    
    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());
        
        A = new int[N];
        result = new int[M];
        visited = new boolean[N];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A); // 오름차순 출력 위한 정렬
 
        dfs(0, 0);      // 🔔 (0, 0)부터 시작
        System.out.println(sb);
    }
    
    private static void dfs(int at, int depth) {
        if(depth == M) {
            for(int i = 0 ; i < M ; i++) {
                sb.append(result[i] + " ");
            }
            sb.append("\n");
            return;
        }
        
        for(int i = at ; i < N ; i++) { // at 부터 탐색 시작해야 (7 8 부터 시작)
            if(!visited[i]) {
                visited[i] = true;
                result[depth] = A[i];   // 현재 깊이 위치에 A[i] 값 담기
                dfs(i, depth + 1);      // (재귀)
                visited[i] = false;               
            }
        }
    }
}

✅ 해결 아이디어
✔ 백트래킹 (DFS)

 

이것도 N과 M (2) 문제랑 똑같다.

다른 점은 (0,0)부터 시작한다는 거랑,

dfs 에서 result[depth] 부분에 A[i] 넣는다는 것

 

 

 

 

---

💬 느낀 점

맞다.. 조합 백트래킹....

 

 

1회독	2회독	3회독	4회독	5회독
V	8.29

 

 

(+ 2회독 : 8.29)

내힘내품 !!! (내 힘으로 내가 품..)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[] A, result;
    static StringBuilder sb = new StringBuilder();
    
    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());
        
        A = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A);
        
        result = new int[M];
        
        back(0, 0);
        System.out.println(sb);
    }
    
    private static void back(int startIdx, int depth) {
        if(depth == M) {
            for(int i : result) sb.append(i).append(" ");
            sb.append("\n");
            return;
        }
        
        for(int i = startIdx ; i < N ; i++) { // 오름차순 정렬
            result[depth] = A[i];
            back(i + 1, depth + 1); // i + 1로 해야 (1 1) (7 7) 이런 경우가 사라짐
        }
    }
}

 

---

(참고)

[ 백준 15655 / Java ] N과 M (6)

[문제] 백준 15655번 N과 M (6) - Java