[프로그레머스/C++] 양궁대회

 

https://scool.programmers.co.kr/learn/courses/30/lessons/92342

 

문제 요약

카카오배 양궁대회 결승전에서 라이언과 어피치가 맞붙게 됩니다. 이번 결승전 규칙은 전 대회 우승자인 라이언에게 불리하게 설정되어 있습니다. 각 선수는 과녁 점수(0~10점)에 화살을 맞힌 후, 더 많은 화살을 맞힌 쪽이 그 점수를 가져갑니다. 동점일 경우 어피치가 점수를 가져가며, 두 사람 모두 맞추지 못한 경우에는 점수가 없습니다.

라이언이 어피치를 가장 큰 점수 차이로 이기기 위해 n발의 화살을 어떻게 쏴야 하는지 구하는 문제입니다. 만약 라이언이 우승할 수 없는 경우에는 -1을 반환합니다.

문제 핵심

1. 점수 계산 방식: 어피치가 맞힌 화살과 라이언이 맞힌 화살을 비교하여, 더 많은 화살을 맞힌 쪽이 해당 점수를 가져갑니다.
2. 동점 처리: 동점일 경우 어피치가 점수를 가져갑니다.
3. 최대 점수 차이: 라이언이 어피치보다 더 많은 점수를 얻는 상황을 구해야 합니다.
4. 다양한 경우의 수 탐색: 화살을 n발 모두 쏴야 하며, 여러 가지 경우의 수를 고려하여 라이언이 가장 큰 점수 차이로 이길 수 있는 경우를 찾아야 합니다.

문제 풀이 접근 방법

1. 완전 탐색(DFS)

이 문제는 여러 가지 경우의 수를 고려해야 하므로 완전 탐색으로 모든 경우를 탐색하는 방식으로 해결할 수 있습니다. dfs 함수로 라이언이 각 과녁에 몇 발의 화살을 쏠지 결정하고, 그 결과를 계산해 점수 차이가 가장 큰 경우를 선택합니다.

2. 라이언과 어피치의 점수 계산

라이언이 이길 수 있는 방법을 탐색하는 중간에 각 경우의 점수 차이를 계산하여 가장 큰 점수 차이로 이길 수 있는 방법을 찾습니다. 이를 위해 calc 함수를 사용합니다.

3. 최적의 경우 선택

여러 가지 경우가 나올 수 있는데, 가장 낮은 점수를 더 많이 맞힌 경우를 우선 선택해야 하므로, 동점일 경우 추가 조건을 고려하여 결과를 선택합니다.

4. 우승 불가 시 처리

만약 라이언이 이길 수 없는 경우에는 -1을 반환합니다.

5. 각 idx 마다 라이언의 최적 화살 수는 apeach + 1개

어피치가 쏜 화살 수 + 1 개의 화살을 해당 구간에 쏘면, 라이언은 어피치보다 더 많이 쏜 것이 되어 그 점수를 가져갑니다. ex) 어피치가 10점에 1발을 쏜 상황에서 라이언이 10점에 10발을 다 쏘든 2발만 쏘든 라이언이 10점을 가져가기 때문에 최적은 어피치 + 1 인 2점.

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> answer;
int maxPoint = -1;

void calc(vector<int> ryan, vector<int> apeach){
    int ryanPoint = 0;
    int apeachPoint = 0;

    for(int i = 0; i<11; i++){
        if(ryan[i] == 0 && apeach[i] == 0) continue;
        if(ryan[i] <= apeach[i]){
            apeachPoint += (10 - i);
        }else{
            ryanPoint += (10 - i);
        }
    }
    int diff = ryanPoint - apeachPoint;
    if(diff > 0 && diff >= maxPoint){
        if(diff == maxPoint){
            for(int i = 10; i >= 0; i--){
                if(answer[i] != ryan[i]){
                    if(ryan[i] > answer[i]){
                        answer = ryan;
                    }
                    break;
                }
            }
        }else{
            answer = ryan;
            maxPoint = diff;
        }
    }
}

void dfs(vector<int> ryan, vector<int> apeach, int arrows, int idx){
    if(idx == 11) {
        ryan[10] += arrows;
        calc(ryan, apeach);
        return;
    }

    dfs(ryan, apeach, arrows, idx + 1);

    if(apeach[idx] < arrows){
        ryan[idx] = apeach[idx] + 1;
        arrows -= ryan[idx];
        dfs(ryan, apeach, arrows, idx + 1);
    }

}
vector<int> solution(int n, vector<int> info) {

    vector<int> tmp(11, 0);
    dfs(tmp, info, n, 0);
    if(maxPoint == -1 ) answer.push_back(-1);
    return answer;
}

 

비트마스킹으로도 풀 수 있을꺼 같은데 나중에 한번 해봐야 겠다.