https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
재귀를 이용한 조합!!
재귀는 3단계
1. 정답
2. 불가능한 경우
3. 다음 경우
https://www.acmicpc.net/problem/1759
1759번: 암호 만들기
첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.
www.acmicpc.net
go(n, alpha, password + alpha[i], i + 1);
go(n, alpha, password, i + 1);
기억하자... 재귀를 이용한 조합
나머지는 그냥 거리 구하고 최솟값 구하기이다...
1. 집과 치킨 가게의 좌표를 벡터로 저장.
2. selectChickens(int idx, int cnt)
재귀를 이용한 조합
시작은 selectChickens(0, 0);
2. 치킨 거리
모든 집의 치킨 거리의 합
for (const auto& house : houses)
좌표를 저장하고 있으니까
for-each 문과 auto를 사용
<소스 코드>
|
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
int map[55][55];
// 거리가 아무리 커봤자 이 숫자는 못넘음
int BIG = 987654321;
int ans = 987654321;
vector<pair<int, int>> houses;
vector<pair<int, int>> chickens;
vector<int> selected;
int ChickenDistance()
{
int total = 0;
// for-each 문
// 모든 집을 순회
for (const auto& house : houses)
{
int mindist = BIG;
// 선택된 치킨 가게들과의 거리 중
// 최소를 골라서
for (const auto& idx : selected)
{
int distance = abs(house.first - chickens[idx].first) + abs(house.second - chickens[idx].second);
mindist = min(mindist, distance);
}
// 더해준다
total += mindist;
}
return total;
}
void selectChickens(int idx, int cnt)
{
// 0부터 출발했으므로
if (cnt == m)
{
int distance = ChickenDistance();
// ans와 비교
ans = min(ans, distance);
return;
}
// 더 이상 선택할 치킨집이 없는 경우
if (idx == chickens.size())
return;
// 재귀를 이용한 조합
//현재 치킨집 선택 cnt + 1로 넘긴다
selected.push_back(idx);
selectChickens(idx + 1, cnt + 1);
// 현재 치킨집 선택하지 않음 cnt로 넘긴다
selected.pop_back();
selectChickens(idx + 1, cnt);
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> map[i][j];
if (map[i][j] == 1)
houses.push_back(make_pair(i, j));
else if (map[i][j] == 2)
chickens.push_back(make_pair(i, j));
}
}
// 0번 인덱스, 0개 선택
selectChickens(0, 0);
cout << ans << '\n';
return 0;
}
|
cs |
