|
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
|
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int Info[11];
int cnt[11];
vector<vector<int> > ans;
vector<int> answer;
int score=0;
// 작은 점수에 더 많은 화살이 있는지
bool isBetter() {
for(int i=10; i>=0; i--) {
if(cnt[i] > answer[i]) return true;
else if(cnt[i] < answer[i]) return false;
}
}
int totR(){
int tmp=0;
for(int i=0;i<=10;i++){
if(Info[i]==0 && cnt[i]==0)
continue;
if(Info[i]<cnt[i])
tmp+=10-(i);
}
return tmp;
}
int totA(){
int tmp=0;
for(int i=0;i<=10;i++){
if(Info[i]==0 && cnt[i]==0)
continue;
if(Info[i]>=cnt[i])
tmp+=10-(i);
}
return tmp;
}
void DFS(int pos,int n){
if(pos>10)
return;
if(n<0)
return;
if(pos==10 && n>0){
cnt[pos]=n;
DFS(pos,0);
cnt[pos]=0;
return;
}
if(n==0){
int tR=totR();
int tA=totA();
if(tA<tR){
if(score<(tR-tA)){
score=(tR-tA);
answer.clear();
for(int i=0;i<=10;i++)
answer.push_back(cnt[i]);
}else if(score!=0 && score==(tR-tA)){
if(isBetter()){
answer.clear();
for(int i=0;i<=10;i++)
answer.push_back(cnt[i]);
}
}
}
return;
}
DFS(pos+1,n);
cnt[pos]=Info[pos]+1;
DFS(pos+1,n-(Info[pos]+1) );
cnt[pos]=0;
}
vector<int> solution(int n, vector<int> info) {
N=n;
for(int i=0;i<info.size();i++)
Info[i]=info[i];
DFS(0,n);
if(answer.empty()){
answer.push_back(-1);
return answer;
}
return answer;
}
|
cs |
출처: https://school.programmers.co.kr/learn/courses/30/lessons/92342
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
완전탐색으로도 풀 수 있는 문제입니다.
test case 8,18번이 자꾸 실패가 떴었는데
isBetter함수로 만약 같은 점수차이로 갱신 시 -> 낮은 점수를 더 많이 쏜 쪽이 출력되게 검증해서 정답 받았습니다.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [c++] 단속카메라 (그리디, 탐욕법) (0) | 2022.09.23 |
|---|---|
| [c++] 야근 지수 (1) | 2022.09.23 |
| [c++] 셔틀버스 (1) | 2022.09.21 |
| [c++] 보석 쇼핑 (1) | 2022.09.20 |
| [c++] 숫자게임 (1) | 2022.09.20 |