[프로그래머스 2레벨] 양궁대회 (C++)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int maxdiff = 0;
vector<int> answer;

void dfs(int idx, int arrows, vector<int> lion, vector<int> apeach) {
    //마지막 과녁까지 탐색했거나 화살을 다 쓴 경우
    if (idx == 11 || arrows == 0) 
    {
        if (arrows > 0) lion[10] += arrows; //남은 화살 0점에 넣기

        int lionScore = 0, apeachScore = 0;

        for (int i = 0; i < 11; i++) 
        {
            if (lion[i] == 0 && apeach[i] == 0) continue;

            if (lion[i] > apeach[i]) lionScore += 10 - i; //라이언 점수
            else apeachScore += 10 - i; //어피치 점수
        }

        if (lionScore > apeachScore) //점수 차 갱신
        {
            int diff = lionScore - apeachScore;
            if (diff > maxdiff) 
            {
                maxdiff = diff;
                answer = lion;
            }
            else if (diff == maxdiff) //점수 차가 같은 경우
            {
                for (int i = 10; i >= 0; i--) //낮은 점수부터 비교
                {
                    if (lion[i] > answer[i]) //낮은 점수가 더 많은 경우 
                    {
                        answer = lion;
                        break;
                    }
                    else if (lion[i] < answer[i]) break;
                }
            }
        }

        return;
    }

    //해당 점수 획득
    if (arrows > apeach[idx])
    {
        lion[idx] = apeach[idx] + 1;
        dfs(idx + 1, arrows - lion[idx], lion, apeach);
        lion[idx] = 0; // 백트래킹
    }

    //해당 점수 포기
    dfs(idx + 1, arrows, lion, apeach);
}

vector<int> solution(int n, vector<int> info) {
    vector<int> lion(11, 0);
    dfs(0, n, lion, info);
    if (answer.empty()) return {-1}; //지거나 비기는 경우
    return answer;
}

 

문제에 주어진 조건에 따라 dfs를 통해 완전 탐색을 하는 문제이다.

별도로 lion용 벡터를 선언하고, 현재 점수를 획득하거나 포기하며 dfs를 돌려준다.

점수판 끝까지 가거나, 화살을 모두 사용하면 종료하며, 이때 점수 차를 체크하여 낮은 점수가 더 많은 경우의 정답을 저장한다.

 

dfs에 넘겨주는 값은 인덱스, 화살 개수, lion, apeach이다.

점수를 획득하는 경우는 우선 화살 개수가 어피치가 해당 점수에 맞힌 화살 개수보다 많아야 할 것이다.

많기만 하면 되기에, 조건 체크 후 어피치의 화살 개수보다 + 1을 하여 저장해준다.

그리고 다음 점수를 탐색하는데, 사용한 화살은 감소시켜 넘겨준다.

그리고 백트래킹을 통해 다른 경우의 수에서도 탐색이 가능하도록 해준다.

 

점수 포기의 경우는 간단하게 현재 화살개수를 유지하며 바로 다음 점수로 넘어가면 된다.

 

이제 마지막 과녁까지 탐색했거나, 화살을 다 쓴 경우이다.

먼저 마지막 과녁까지 탐색했는데, 화살이 남은 경우에는 화살을 무조건 다 써야 하기에 0점 과녁에 몰아서 저장한다. 

0점에 넣는 이유는, 점수에 영향이 없기 때문이다.

 

이후 lion과 apeach의 점수를 계산하여 저장해주고, 이를 토대로 라이언 점수가 더 높을 때 점수 차 값을 계산한다.

해당 경우 우선 라이언이 이겼기에 라이언을 정답 배열에 저장하고, 가장 큰 점수 차이 체크를 위해 점수 차 값도 갱신해주어야 한다.

 

만약 점수 차가 같은 경우는 낮은 점수부터 비교해야 한다.

이때는 뒤에서 부터 탐색(0점부터)하며 낮은 점수가 기존 정답보다 더 많은 경우 바로 현재 벡터를 정답에 저장하고 종료시킨다.

만약 기존 정답 배열이 더 많다면, 갱신이 불가하기에 마찬가지로 바로 종료시킨다.