개발일지/Algorithm
백준 - 15652 N과 M (4) [백트래킹]
E-room
2023. 9. 28. 18:02
728x90
15652번: N과 M (4)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
1. 문제 요약
1부터 N까지의 자연수를 사용하여 길이가 M인 수열을 생성하라
- 같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다.
- 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
2. 접근 방법
재귀 함수를 사용합니다.
15650(조합) 과 15651 을 적절히 섞으면 됩니다.
3. 파이썬
from sys import stdin
input = stdin.readline
def solution(start: int, depth: int):
if depth == M:
print(' '.join(map(str, arr)))
return
for i in range(start, N + 1):
arr[depth] = i
solution(i, depth + 1)
N, M = map(int, input().split())
arr = [0] * M
solution(1, 0)
4. 자바
static int N, M;
static int[] arr;
static StringBuilder sb = new StringBuilder();
static void solution(int start, int depth) {
if (depth == M) {
for (int i : arr) {
sb.append(i).append(' ');
}
sb.append('\n');
return;
}
for (int i = start; i <= N; i++) {
arr[depth] = i;
solution(i, depth + 1);
}
}
// solution(1, 0);
5. 전체 코드
728x90