개발일지/Algorithm
백준 - 15650 N과 M (2) [조합]
E-room
2023. 9. 27. 18:38
728x90
14719번: 빗물
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치
www.acmicpc.net
1. 문제 요약
1부터 N까지의 숫자들 중 M개를 뽑아 조합(Combination)을 만드는 문제입니다.
2. 접근 방법
조합을 생성하는 대표적인 방법으로 재귀함수를 이용할 수 있습니다.
3. 파이썬
from sys import stdin
input = stdin.readline
def solution(start: int, depth: int):
if depth == M:
print(*arr)
return
for i in range(start, N):
if not visit[i]:
visit[i] = True
arr[depth] = i + 1
solution(i + 1, depth + 1)
visit[i] = False
N, M = map(int, input().split())
arr = [0] * M
visit = [False] * N
solution(0, 0)추가로 itertools.combinations 함수를 이용할 수 도 있습니다.
4. 자바
static int N, M;
static int[] arr;
static boolean[] visit;
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++) {
if (!visit[i]) {
visit[i] = true;
arr[depth] = i + 1;
solution(i + 1, depth + 1);
visit[i] = false;
}
}
}
5. 전체 코드
728x90