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;
}
}
}
}
❤ 회고

다섯 달전에도 풀었던 걸 잠깐 안풀어주면 까먹는 저랍니다 ~! 📈 까마귀 고기 까악까악 -
이젠 정말... 안까먹겠어요..
'[Algorithm] 알고리즘' 카테고리의 다른 글
| [백준][boj] A → B(16953) - JAVA (1) | 2025.01.23 |
|---|---|
| [백준][boj] 멀티탭 스케줄링(1700) - JAVA (1) | 2025.01.13 |
| [프로그래머스][JAVA] 조이스틱 - 그리디 (1) | 2025.01.06 |
| [프로그래머스] 체육복 (JAVA) (1) | 2024.12.27 |
| [백준][boj]가르침 (JAVA) - 완전탐색의 유연한 생각 (1) | 2024.12.23 |