[2022 KAKAO BLIND RECRUITMENT] 양궁대회

[uijin-j]

🔗 양궁대회

[hye-on]

• Language : C++
• 성능

코드 풀이

```cpp #include #include #include #include using namespace std; //08:52 //0은 양, 1은 늑대 // visit처리 땜에 dfs //양 쪽의 최대 양을 가져올 수 있는 개수 #include #include #include #include using namespace std; //k점에 맞힌 선수가 k 점을 가져감. 같으면 어피치가 가져감 //종 점수가 같을 경우 어피치를 우승자로 결정 //라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 //많이 맞힌 경우 //투 포인터? // 백트래킹! int p[11]; int sum =55; int mySum =0; int maxS; vector ans(11); vector result(11); vector info; void checkAns(vector num){ int yourS =0; int myS =0; for(int i=0;i<11;i++){ int score = 10-i; if(info[i]=num[i] && info[i]>=1){ yourS+=score; } } if(myS>yourS){ if(myS-yourS>maxS){ //가장 큰 점수 차이 maxS = myS-yourS; ans = num; }else if(myS-yourS == maxS){ for(int i=10;i>=0;i--){ if(ans[i]>num[i]) return; else if(ans[i]num){ if(rn<0){ return; } if(depth==11){ //답이 될 수 있는지 체크 if(rn>0) num[10] =rn; checkAns(num); return; } int t = info[depth]+1; num[depth] = t; recursion(depth +1 ,rn-t , num); //과녁 맞춤 num[depth] =0; recursion(depth +1 ,rn , num); // 과녁 못맞춤 } vector solution(int n, vector _info) { vector answer; info = _info; recursion(0,n,result); for(int i=0;i<11;i++) if(ans[i]>=1) return ans; answer.push_back(-1); return answer; } ```

코멘트

- 투포인터로 접근했다가 아니였고 결국 백트래킹을 이용한 완탐 + 조건 꼼꼼히 읽기 였던 것 같습니다.
- 가장 큰 점수가 아니라 <가장 큰 점수차이>를 놓쳤었네요.. 카카오는 문제 꼼꼼히..

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.util.*; // 16:42 START! // 어렵당.. class Solution { /** * 보자마자 배낭 문제가 생각남! (이득을 얻기 위해 손실도 있음) * - 써야하는 화살 => 손실 => 배낭 문제에서 무게 * - 얻을 수 있는 점수 => 이득 => 배낭 문제에서 가치 * * 결국 풀이를 봤더니.. 완탐문제였다.. */ int[] ryan = new int[11]; int[] apeach = new int[11]; int[] answer = new int[11]; int maxDiff = 0; public int[] solution(int n, int[] info) { apeach = info; dfs(0, n); return maxDiff == 0 ? new int[]{-1} : answer; } private void dfs(int level, int remain) { if(level == 10) { ryan[10] = remain; // 남은 화살은 0에 쏘기 int rScore = 0; int aScore = 0; for(int i = 0; i <= 10; ++i) { if(ryan[i] > apeach[i]) rScore += 10 - i; else if(apeach[i] > 0) aScore += 10 - i; } if(rScore - aScore > maxDiff) { maxDiff = rScore - aScore; answer = copy(ryan); } if(rScore - aScore == maxDiff) { for(int i = 10; i >= 0; --i) { if(ryan[i] > answer[i]) { answer = copy(ryan); break; } if(answer[i] > ryan[i]) break; } } return; } // level 과녁을 라이언이 맞춤 if(apeach[level] + 1 <= remain) { ryan[level] = apeach[level] + 1; dfs(level + 1, remain - (apeach[level] + 1)); ryan[level] = 0; } // level 과녁을 라이언이 안 맞춤 dfs(level + 1, remain); } public int[] copy(int[] arr) { int[] answer = new int[11]; for(int i = 0; i <= 10; ++i) { answer[i] = arr[i]; } return answer; } } ```

코멘트

- n이 작아서 완탐으로 풀 수 있는데, 괜히 더 어렵게 접근했네요🥲 항상 시간 복잡도를 먼저 계산해야 될 것 같네용..