[문제]
https://www.acmicpc.net/problem/18429
18429번: 근손실
웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로
www.acmicpc.net
[문제 풀이]
백트래킹을 사용하는 도중에 모든 경우에 500이하가 되는지 아닌지를 확인해주자.
벡터에 n만큼 숫자가 찼을 경우에 (16~)
벡터 크기만큼 돌려서 현재 벡터에 저장되어있는 숫자를 더하고 k만큼 뺐을때 500이 넘는지 아닌지 확인해주자. (20~27)
만일 숫자가 계속해서 500을 넘는다면 answer의 카운트를 올려주자. (28~30)
n만큼 돌렸을때 위치를 방문했는지 안했는지를 확인하고 방문을 안했다면 방문체크를 한 뒤에 재귀를 돌리자. (34~41)
재귀가 돌아가고 나면 원래 넣었던 숫자를 빼고 현재 위치를 방문하지 않은걸로 바꾸자.(42~43)
[코드]
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
|
#include<iostream>
#include<vector>
#define endl "\n"
using namespace std;
bool visit[9];
int health[10];
int n,k;
int total = 500;
int answer;
vector<int> kit;
void backtracking(int m){
if(m == n){
total = 500;
int flag = 1;
for(int i =0;i<kit.size();i++){
total += kit[i];
total -= k;
if(total < 500){
flag = 0;
break;
}
}
if(flag == 1){
answer += 1;
}
return;
}
for(int i = 0;i<n;i++){
if(visit[i] == true){
continue;
}
visit[i] = true;
kit.push_back(health[i]);
backtracking(m+1);
kit.pop_back();
visit[i] = false;
}
}
int main(){
cin>>n>>k;
for(int i = 0;i<n;i++){
cin>>health[i];
}
backtracking(0);
cout<<answer<<endl;
return 0;
}
|
cs |