[백준][boj]N과 M(5) - JAVA

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

 

 

 

✔ 문제 풀이

재귀의 정석인 N과 M시리즈 5를 모셨습니다.

매번 느끼지만 아무래도 알고리즘은 파이썬이 짱인듯해요 ! 

 

재귀에서 가장 중요한 것은 종료조건 설정(return)

여기에서 종료조건은 👉 result (우리가 출력할 배열)의 크기가 M개인 것 (M개를 뽑기 때문이다).

 

그 이외는 배열을 미리 정렬해줄 것.

중복된 숫자를 뽑지 않기 위해 방문배열을 기록해줄 것이다 ~~!

 

이해하기 어렵다면 N과 M 시리즈를 처음부터 풀어보는 것을 추천한다.

https://www.acmicpc.net/workbook/view/2052

 

    static void dp(int depth){

		// 종료조건 : M개만 뽑을 것
        if(depth == M){
            for(int a: result){
                System.out.print(a+" ");
            }
            System.out.println();
            return;
        }

        for(int i=0; i<N; i++){
        	// 중복 체크 ✔ 아직 안뽑은 숫자만!
            if(!visited[i]){
                visited[i] = true;
                result[depth] = arr[i];
                dp(depth+1);
                visited[i] = false;
            }
        }
    }

 

 

---

 

✔ 전체 코드

import java.util.*;
import java.io.*;

public class Main {
    static int N;
    static int M;
    static int [] arr;
    static boolean [] visited;
    static int [] result;

    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[N];
        visited = new boolean[N];
        result = new int[M];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        dp(0);
    }

    static void dp(int depth){

        if(depth == M){
            for(int a: result){
                System.out.print(a+" ");
            }
            System.out.println();
            return;
        }

        for(int i=0; i<N; i++){
            if(!visited[i]){
                visited[i] = true;
                result[depth] = arr[i];
                dp(depth+1);
                visited[i] = false;
            }
        }
    }
}

 

 

 

---

 

 

❤ 회고

 

다섯 달전에도 풀었던 걸 잠깐 안풀어주면 까먹는 저랍니다 ~! 📈 까마귀 고기 까악까악 - 

 

이젠 정말... 안까먹겠어요..