백준: N과 M
문제
설명
- 1부터
N
까지의 카드 중에서M
개를 뽑는 경우의 수를 구하라! - 단, 순서가 있음을 주의
- 즉,
1 4
와4 1
은 다른 것으로 취급
- 즉,
알고리즘
n_array
,used_n
선언- 첫 번째 변수는 출력할 수를 담기 위한 벡터[길이 = M]
- 두 번째 변수는
이 수를 방문 했는가?
를 확인하기 위한 벡터[길이 = N]
dfs(depth)
시작[depth 초기값 = 0]- 만약
depth == M
이라면- n_array에 있는 내용을 출력하고 리턴
- 아니라면
i = 0; i < n; i++
반복문 실행- 만약 탐방하지 않은 수가 있다면
- 해당 수를 탐방했다고 표시하고
dfs(depth+1)
실행 - 실행 후 탐방을 하지 '않았다고' 표시함[왜냐: 순서가 있기 때문!]
- 해당 수를 탐방했다고 표시하고
- 만약 탐방하지 않은 수가 있다면
코드
- 만약
#include <vector>
#include <cstdio>
using namespace std;
vector<bool> used_n;
vector<int> n_array;
int n, depth;
void dfs(int cur_depth) {
if (cur_depth == depth) {
for (int tmp : n_array) {
printf("%d ", tmp);
}
printf("\n");
return;
}
for (int i = 0; i < n; i++) {
if (!used_n[i]) {
used_n[i] = true;
n_array[cur_depth] = i+1;
dfs(cur_depth + 1);
used_n[i] = false;
}
}
}
int main(void) {
scanf("%d %d", &n, &depth);
// Resize Used
used_n.resize(n, false);
// Init Vector
n_array.resize(depth, 0);
dfs(0);
return 0;
}
Author And Source
이 문제에 관하여(백준: N과 M), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kangdroid/백준-N과-M저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)