[백준] 15651번 / Java, Python
Baekjoon Online Judge
algorithm practice
단계별 문제풀기
13. 백트래킹
모든 경우를 탐색하는 백트래킹 알고리즘을 배워 봅시다.
모든 경우를 탐색하는 백트래킹 알고리즘을 배워 봅시다.
Java / Python
3. N과 M (3)
백트래킹 입문 문제 3
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- N과 M(1) 예제에서 같은 수 중복 제거 조건을 뺀 문제입니다.
- Java
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static int[] arr;
public 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());
// 공백을 기준으로 입력받기 때문에 공백 구분을 위해 StringTokenizer 객체를 함께 사용
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[M];
dfs(0);
System.out.println(sb);
}
public static void dfs(int depth) {
if (depth == M) {
for (int i = 0; i < M; i++) {
sb.append(arr[i]).append(' ');
}
sb.append('\n');
return;
}
for (int i = 1; i <= N; i++) {
arr[depth] = i;
dfs(depth + 1);
}
}
}
수행시간을 빠르게 하기 위해 BufferedReader와 StringBuilder를 이용했습니다.
- Python
N, M = map(int, input().split())
result = []
def dfs(depth, N, M):
if depth == M:
print(' '.join(map(str, result)))
return
for i in range(N):
result.append(i+1)
dfs(depth+1, N, M)
result.pop()
dfs(0, N, M)
백트래킹에 대해서도 자세히 정리하려고 합니다.
Author And Source
이 문제에 관하여([백준] 15651번 / Java, Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jini_eun/백준-15651번-Java-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)