반응형
이번에는 백준 15652번 문제를 통해 백트래킹 알고리즘 학습을 강화해 보자.
N과 M의 최종문제이다. 지금까지 문제를 생각해보면 이 문제도 15651번 문제 처럼 아주 쉽게 풀 수 있다.
문제 핵심
- 1부터 N까지의 자연수 중 중복 없이 M개를 고른 수열
- 1 <= M <= N <= 8
- 중복하여 방문 가능
- 이전의 수보다 작지만 않으면 됨 ( 같은 수여도 가능 )
풀이 과정
지금까지 풀이 1, 2, 3문제를 보았다면 아주 쉽게 접근할 수 있다.
이전 문제의 이론은? "모든 경로가 중복 방문이 가능하다면? 다시 처음부터 시작하면 된다." 였다.
그렇다면 우리는 해당 숫자부터 즉, 1이면 1부터 2이면 2부터 그대로 값을 전달해주면 된다.
이전 문제에서 고정시켰던 값을 다시 변동 시켜 계속 전달해주면 된다.
핵심 코드를 살펴보자
핵심 코드
다음 반복문에서 i 값을 그대로 전달해주는 것을 알 수 있다.
그렇게 되면 2인 값이 그대로 2로 전달되고 start매개변수를 통해 (M = 3, N = 3 인 경우) 1, 2, 2 와 같은 값을 얻을 수 있다.
private static void backTracking(int depth, int M, int N, int start) {
if (depth == M) {
for (int i : arr) {
stringBuilder.append(i).append(" ");
}
stringBuilder.append("\n");
return;
}
for (int i = start; i < N; i++) {
arr[depth] = i + 1;
backTracking(depth + 1, M, N, i);
}
}이제는 정말로 쉽게 풀이될 것이라고 생각한다.
이번 4개의 N과 M의 문제를 통해 충분히 학습될 것이라고 생각한다.
하지만 백트래킹이라고 해서 한 가지 유형만 있는 것은 아니니 몇 개 안남은 단계 문제를 풀고,
이후 다른 백트래킹 문제도 풀어보는 것이 좋겠다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int[] arr;
private static StringBuilder stringBuilder = new StringBuilder();
private static void backTracking(int depth, int M, int N, int start) {
if (depth == M) {
for (int i : arr) {
stringBuilder.append(i).append(" ");
}
stringBuilder.append("\n");
return;
}
for (int i = start; i < N; i++) {
arr[depth] = i + 1;
backTracking(depth + 1, M, N, i);
}
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int N = Integer.parseInt(stringTokenizer.nextToken());
int M = Integer.parseInt(stringTokenizer.nextToken());
arr = new int[M];
backTracking(0, M, N, 0);
System.out.println(stringBuilder);
}
}
반응형
'백준 단계별 풀이' 카테고리의 다른 글
| [ 백준 2439번 문제 ] 별 찍기 - 2 - JAVA (2) | 2025.06.11 |
|---|---|
| [ 백준 2438번 문제 ] 별 찍기 - 1 - JAVA (1) | 2025.06.10 |
| [ 백준 15651번 문제 ] N과 M (3) - JAVA (1) | 2025.05.24 |
| [ 백준 15650번 문제 ] N과 M (2) - JAVA (1) | 2025.05.23 |
| [ 백준 24060번 문제 ] 알고리즘 수업 - 병합 정렬 1 - JAVA (2) | 2025.05.21 |
