⚙️ 알고리즘 분류 : 완전탐색
🔠 언어 : c++
🤫 힌트.
문제를 잘 읽어보자. 하란 대로 하면 된다.
✏️ 풀이.
dfs로 접근해야겠다는 생각도 잘 안 났다.
딱 보자마자 knapsack이군..! 이라고 생각했다.
문제 풀이 단계
(1) 라이언이 해당 점수에 쏜 경우와 안 쏜 경우 각각을 dfs 재귀로 돌린다.
(1-1) 쏜 경우엔 남은 화살 개수를 체크해야 한다.
(2) 만약 더 이상 쓸 화살이 없거나, 모든 점수에 화살 배치한 경우엔 점수 계산을 한다.
(2-1) 현재 점수 차이가 이전의 점수 차이보다 크거나 같을 경우, 값을 갱신해준다.
(2-2) 같을 경우엔, 낮은 점수에 더 많은 쏜 경우를 저장하도록 한다.
⚠️ 헤맨 부분.
1) 어피치와 가장 큰 점수 차이
문제에서 대놓고 라이언은 어피치를 가장 큰 점수 차이로 이기기 위해서 라고 주어졌다. 따라서 어떠한 max 값을 저장해야 한다면, 여기서 '어떠한'은 어피치와의 점수 차이가 된다.
나는 점수 차이로 안 하고, 라이언의 가장 큰 점수를 저장하도록 했다. 그랬더니 왕창 틀려버렸다.
처음엔 왜 틀렸는지 이해하지 못했지만, 차근차근 생각해보니 내 생각에 오류가 있었다...!
나는 어피치의 점수가 항상 동일하다고 생각했다.
어피치가 쏜 화살 개수가 동일한 거지, 점수는 라이언 화살 개수에 따라서 달라진다.
이를 생각하니까 왜 틀렸는지 알 수 있었다. 이젠 문제에서 하란 대로 해야지ㅠ
2) 네 상대는 어피치가 아니라, 과거의 너라구!
점수가 같으면 낮은 점수에 많이 투자한 답이 우선시 된다.
만약 새로 구한 값이 기존의 정답 값과 동일하다면, 기존의 값과 비교해야 한다.
움 근데 나는 어피치와 비교해버렸다... 이건 집중의 문제인 것 같다.
일전에 어떤 회사의 면접에서도, 이런 식으로 문제 파악을 제대로 못했는데...
스스로 고쳐야 할 점인 걸 잘 알고 있지만, 잘 되지 않아서 속상하다... 어떻게 하면 좋을까?
👩🏻💻 코드.
#include <string>
#include <vector>
#include <iostream>
#define mp make_pair
using namespace std;
vector<int> answer, apeach;
vector<int> ryan(11,0);
int mx=0;
bool cmp(){
for(int i=10; i>=0; i--){
// POINT 1. 기존 값과 비교
if(ryan[i]>answer[i]) return true;
if(answer[i]>ryan[i]) return false;
}
return false;
}
void cal(){
int a_score=0, r_score=0;
for(int i=0; i<=10; i++){
if(apeach[i]==0 && ryan[i]==0) continue;
if(apeach[i]>=ryan[i]) a_score+=(10-i);
else r_score+=(10-i);
}
// POINT 2. 차이 값의 최대를 저장
if(a_score<r_score && mx<=(r_score-a_score)){
if(mx==(r_score-a_score) && !cmp()) return;
mx=(r_score-a_score);
answer=ryan;
}
}
void dfs(int cnt, int remain){
if(cnt==11 || remain==0){
ryan[10]=remain;
cal();
ryan[10]=0;
return;
}
int shoot=apeach[cnt]+1;
if(remain-shoot>=0){
ryan[cnt]=shoot;
dfs(cnt+1, remain-shoot);
ryan[cnt]=0;
}
dfs(cnt+1, remain);
}
vector<int> solution(int n, vector<int> info) {
apeach=info;
dfs(0,n);
if(answer.size()==0) answer.push_back(-1);
return answer;
}😎 후기.
예전에 한 번 풀었던 문젠데, 또 헤매버렸다!(엣큥-⭐️)
예전에도 knapsack으로 시작했는데, 이번에도 그랬다.
흠 발전이 없는 걸까...?ㅠㅠ
혼자서 예제 다 맞췄을 땐 기뻤지만, 실제 테스트에선 많이 틀렸다.
실제 공채 시험 상황이었다면 정말 우울 그 자체였을 것 같다.
하... 오쪼지...
