개발일지/Algorithm
백준 - 15656 N과 M (7) [백트래킹]
E-room
2023. 9. 28. 19:03
728x90
1. 문제 요약
주어진 숫자들 중 M개를 골라 오름차순으로 정렬된 수열을 생성하라.
같은 수를 여러 번 사용해도 된다.
2. 접근 방법
- 입력받은 숫자들을 오름차순 정렬
- 재귀함수를 이용하여 수열 생성
3. 파이썬
from sys import stdin
input = stdin.readline
def solution(depth: int):
if depth == M:
print(' '.join(map(str, arr)))
return
for i in range(N):
arr[depth] = nums[i]
solution(depth + 1)
N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
arr = [0] * M
solution(0)
4. 자바
static int N, M;
static int[] nums;
static int[] arr;
static StringBuilder sb = new StringBuilder();
static void solution(int depth) {
if (depth == M) {
for (int i : arr) {
sb.append(i).append(' ');
}
sb.append('\n');
return;
}
for (int i = 0; i < N; i++) {
arr[depth] = nums[i];
solution(depth + 1);
}
}
5. 전체 코드
728x90