반응형
CASE 1) 순서 O, 중복 X
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
#include <stdio.h>
#include <iostream>
using namespace std;
int N, M;
int arr[9];
int ch[9];
void dfs(int depth){
if(depth == M){
for(int i=0; i<M; i++){
printf("%d ", arr[i]);
}
printf("\n");
return;
} else {
for(int i=1; i<=N; i++){
if(ch[i] == 0){
ch[i] = 1;
arr[depth] = i;
dfs(depth + 1);
ch[i] = 0;
}
}
}
}
int main(void) {
cin >> N >> M;
dfs(0);
return 0;
}
- check 배열과 arr 배열, 그리고 depth 를 사용하여 구현하였다.
CASE 2) 순서 X, 중복 X
15650번: N과 M (2)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
#include <stdio.h>
#include <iostream>
using namespace std;
int N, M;
int ch[9];
int arr[9];
void dfs(int s, int depth){
if(depth == M){
for(int i=0; i<M; i++){
printf("%d ", arr[i]);
}
printf("\n");
return;
} else {
for(int i=s; i<=N; i++){
if(ch[i] == 0){
ch[i] = 1;
arr[depth] = i;
dfs(i, depth+1);
ch[i] = 0;
}
}
}
}
int main(void) {
cin >> N >> M;
dfs(1, 0);
return 0;
}
CASE 3) 순서 O, 중복 O
15651번: N과 M (3)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
#include <stdio.h>
#include <iostream>
using namespace std;
int N, M;
int arr[10];
void dfs(int depth){
if(depth == M){
for(int i=0; i<M; i++){
printf("%d ", arr[i]);
}
printf("\n");
return;
} else {
for(int i=1; i<=N; i++){
arr[depth] = i;
dfs(depth+1);
}
}
}
int main(void) {
cin >> N >> M;
dfs(0);
return 0;
}
CASE 4) 순서 X, 중복 O
15652번: N과 M (4)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
#include <stdio.h>
#include <iostream>
using namespace std;
int N, M;
int arr[10];
void dfs(int s, int depth){
if(depth == M){
for(int i=0; i<M; i++){
printf("%d ", arr[i]);
}
printf("\n");
return;
} else {
for(int i=s; i<=N; i++){
arr[depth] = i;
dfs(i, depth+1);
}
}
}
int main(void) {
cin >> N >> M;
dfs(1, 0);
return 0;
}
< 결론 >
순서 X - 0부터 시작
순서 O - s 부터 시작
중복 X - ch 배열 안씀
중복 O - ch 배열 씀
반응형
'Programming > Coding Test' 카테고리의 다른 글
| 9. C++ String 문법 정리 (0) | 2021.01.05 |
|---|---|
| 8. 동적계획법 (0) | 2021.01.02 |
| 6. DFS - 부분집합 (0) | 2020.12.31 |
| 5. STL 정리 (0) | 2020.12.29 |
| [C++] 백준 2573 빙산 - 테스트 케이스 (0) | 2020.11.15 |