[프로그래머스] 양궁대회 C++ - 완전탐색 (2022_카카오)

문제

https://programmers.co.kr/learn/courses/30/lessons/92342
👉🏻 문제에 대한 전체 설명은 링크 참조!!

화살의 개수를 담은 자연수 n, 어피치가 맞힌 과녁 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열 info가 매개변수로 주어집니다. 이때, 라이언이 가장 큰 점수 차이로 우승하기 위해 n발의 화살을 어떤 과녁 점수에 맞혀야 하는지를 10점부터 0점까지 순서대로 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 만약, 라이언이 우승할 수 없는 경우(무조건 지거나 비기는 경우)는 [-1]을 return 해주세요.

풀이방식

우선 라이언이 이길 수 있는 조건을 정리해보자.
👉🏻k점에 어피치가 a개, 라이언이 b개 맞추었고, 이때 a < b인 경우에만 라이언이 k점을 가져갈 수 있다.(a==b,a>b인 경우는 어피치 승리)
👉🏻a=b=0인 경우에는 라이언과 어피치 그 누구도 점수를 획득할 수 있다.

즉, 1번에 의해서 라이언은 어피치와 최대한 큰 점수 차이를 가져야 하고, 어피치가 맞춘 화살의 개수보다 +1 개수를 배치한다.

🧐어떤 방식으로 풀어야 할지?
dfs를 이용하여 완전탐색 방식으로 풀어야 한다는 것을 알았지만, 세세하게 어떻게 조건을 나누어서 dfs를 해야할지 감이 잡히지 않았다. 처음에는 테스트케이스 1번만 고려하여 index를 하나씩 옮겨가며 탐색하는 index전에는 화살을 부여하지 않는 방식으로 했다. 그랬더나 당연히 테스트케이스 1번만 맞았다..
풀이를 참고하여 다시 코드를 작성하였다.

함수는 총 3개가 필요하다.
1. 화살을 부여하는 Solve 함수

• 인덱스가 11일 때 남은 화살은 라이언의 마지막 화살에 전부 부여
• 화살을 부여할 수 있는 경우에는 현재 어피치 화살의 개수+1,
  화살을 부여하지 않는 경우에는 인덱스만 +1

   solve(idx+1, arrows-apeach[idx]-1, ryan,apeach);
   solve(idx+1, arrows, ryan, apeach);

2. 부여된 화살의 점수를 계산하는 calcScore 함수
3. 작은 점수에 더 많이 분포되어 있는지 확인하는 cmp함수
   (라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 리턴해야 하기 때문에)

코드

#include <string>
#include <vector>

using namespace std;
vector<int> answer(1,-1);
int maxDiff = 0;

bool cmp(vector<int> ryan) {
    
    for(int i = 10; i >= 0; i--) {
        if(ryan[i] > answer[i]) return true;
        else if (ryan[i] < answer[i]) return false;
    }
}

void calcScore(vector<int> ryan, vector<int> apeach) {
    int ryanScore = 0;
    int apeachScore = 0;
    
    for(int i = 0; i < 11; i++) {
        if(ryan[i] > apeach[i]) ryanScore += 10 - i;
        else if(apeach[i] > 0) apeachScore += 10 - i;
    }
    
    int diff = ryanScore - apeachScore;
    if(diff > 0 && maxDiff <= diff) {
        if(maxDiff == diff && !cmp(ryan)) return;
        maxDiff = diff;
        answer = ryan;
    }
}


void solve(int idx, int arrows, vector<int> ryan, vector<int> apeach) {
    if(idx==11 || arrows == 0) { //분배 끝 
        ryan[10] += arrows;
        calcScore(ryan, apeach);
        ryan[10] -= arrows;
        return;
    }
    if(apeach[idx] < arrows) {
        ryan[idx] += apeach[idx] +1;
        solve(idx+1, arrows-apeach[idx]-1, ryan,apeach);
        ryan[idx] -= apeach[idx] +1;
    }
    solve(idx+1, arrows, ryan, apeach);
}

vector<int> solution(int n, vector<int> info) {
    vector<int> ryan(11,0);
    
    solve(0,n, ryan, info);

    if(answer.empty()) answer.push_back(-1);
    
    return answer;
}

🐥후기

완전탐색에 약한 걸 알고 있었기에 어려웠다. dfs를 여러 조건으로 돌리는 경우, dfs를 하고 다시 제자리로 조건을 돌려줘야한다는 것 이런 점들이 익숙해지지 않는다. 완전탐색 문제를 더 열심히 풀어야 겠다.
(참고한 풀이는 한번 더 풀어보기!)