https://www.acmicpc.net/problem/15650
15650번: N과 M (2)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.
오름차순이므로 for문에서 int i = start
|
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
32
33
34
35
36
37
38
39
40
41
|
#include <iostream>
#include <vector>
using namespace std;
int n, m;
bool c[10];
int a[10];
void go(int cnt, int start)
{
if (cnt == m)
{
for (int i = 0; i < m; i++)
{
cout << a[i];
if (i != m - 1)
cout << ' ';
}
cout << '\n';
return;
}
for (int i = start; i <= n; i++)
{
if (c[i]) continue;
c[i] = true;
a[cnt] = i;
go(cnt + 1, i + 1);
c[i] = false;
}
}
int main()
{
cin >> n >> m;
go(0, 1);
return 0;
}
|
cs |
시간 복잡도는 O(N!)
다른 풀이 (別解) 중요!!!!!!
M개의 수에 어떤 수가 들어갈지를 선택하는 방식으로
1 2 3 ...
o o o ...
x x x ...
시간 복잡도 O(2^N) 훨씬 더 빠름
|
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
32
33
34
35
36
|
#include <iostream>
#include <vector>
using namespace std;
int n, m;
bool c[10];
int a[10];
void go(int selected, int cnt)
{
if (cnt == m)
{
for (int i = 0; i < m; i++)
cout << a[i] << ' ';
cout << '\n';
return;
}
if (selected > n) return;
//결과도 오름차순! a[cnt] = selected;
go(selected + 1, cnt + 1);
a[cnt] = 0;
go(selected + 1, cnt);
}
int main()
{
cin >> n >> m;
go(1, 0);
return 0;
}
|
cs |
a[cnt] = selected;
go(selected + 1, cnt + 1);
a[cnt] = 0;
go(selected + 1, cnt);
고르면 go(cnt + 1)
고르지 않으면 go(cnt)
if (selected > n) return;
예외 처리 필수!
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net