N과 M 수열 문제 시리즈를 하나의 포스트에 정리하려 한다.
수열을 출력하는데, 중복 숫자의 뒤집힌 수열을 포함하는지에 따라 구현 방법이 달라진다.
BOJ 15649 N과 M (1)
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
이 문제는 같은 숫자의 뒤집힌 수열을 포함한다(ex: 1 4, 4 1)
재귀함수를 이용해 백트래킹으로 1~N 까지 숫자를 순차적으로 M개 출력하여 풀 수 있다.
N과 M(1) 소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include<stdio.h>
#include<vector>
using namespace std;
int n,m;
bool nums[10];
void solve(vector<int>& v){
if(v.size() == m) {
for(int i=0;i<v.size();i++){
printf("%d ",v[i]);
}
printf("\n");
return;
}
for(int i=1;i<=n;i++){
if(!nums[i]){
v.push_back(i);
nums[i] = 1;
solve(v);
nums[i] = 0;
v.pop_back();
}
}
}
int main(){
scanf("%d%d",&n,&m);
vector<int>v;
solve(v);
return 0;
}
|
cs |
BOJ 15650 N과 M (2)
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.
이 문제는 같은 숫자의 뒤집힌 수열을 포함하지 않는다. 한 번 나온 숫자의 조합은 한 번만 출력된다.
이런 문제는 순열로 풀 수 있다.
|
1
2
3
4
5
6
|
#include<algorithm>
std::vector<bool> v; // 0 1 0 1
...
std::prev_permutation( v.begin(), v.end() ); // 0 0 1 1
std::next_permutation( v.begin(), v.end() ); // 0 1 1 0
|
cs |
N과 M (2) 소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int n,m;
int main(){
scanf("%d%d",&n,&m);
vector<bool> v(n);
fill(v.begin(), v.begin()+m, 1);
do {
for(int i=0; i<v.size(); i++){
if(v[i])
printf("%d ",i+1);
}
printf("\n");
} while( prev_permutation(v.begin(), v.end()) );
return 0;
}
|
cs |
'알고리즘 문제풀이' 카테고리의 다른 글
| BOJ 4811 알약 (0) | 2020.08.28 |
|---|---|
| BOJ 12865 평범한 배낭 (0) | 2020.08.28 |
| BOJ 2580 스도쿠 (0) | 2020.08.20 |
| BOJ 1194 달이 차오른다, 가자. (0) | 2020.08.11 |
| BOJ 6087 레이저통신 (0) | 2020.08.09 |