[c++][프로그래머스] 양궁대회

프로그래머스 양궁대회 [2022 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/92342

코딩테스트 연습 - 양궁대회

문제 풀이

• 라이언은 전 대회 우승자 페널티로 어피치보다 최소 한 발을 더 맞춰야 과녁 점수를 얻을 수 있습니다. 그렇기 때문에 라이언은 어피치보다 높은 점수를 얻기 위해 다음 두 가지 행동을 할 수 있습니다.
  • 어피치보다 한 발 더 맞춘다.
  • 화살을 쏘지 않고 다음 과녁으로 넘어간다.
• 위의 과정을 거쳐서 10점부터 0점 과녁까지 화살을 다 쏘게 되면 라이언과 어피치의 점수를 계산해야 합니다. 둘 다 0발을 쏜 과녁은 둘 다 점수를 얻지 못하고, 라이언은 전 대회 우승자 페널티를 받기 때문에 (어피치 >=  라이언) 인 경우 어피치가, (어피치 < 라이언) 인 경우 라이언이 점수를 얻습니다. 우리는 라이언이 가장 큰 점수 차이로 우승하는 경우를 구해야 하기 때문에 라이언이 점수가 더 높을 경우 (라이언 점수 - 어피치 점수)를 리턴합니다. 
• 다음 요구 사항으로 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 리턴해야 합니다. 현재까지 가장 높았던 점수와 현재 점수가 같다면 두 과녁 정보 어레이를 뒤에서 부터(0점 부터) 비교하여 현재 어레이가 더 크다면 true, 가장 높았던 점수의 어레이가 더 크다면 false를 리턴 해 줍니다.  (현재까지 가장 높았던 점수보다 현재 점수가 더 크다면 그대로 업데이트) 
• 마지막으로 모든 경우의 수에서 라이언이 어피치를 이기지 못한다면 {-1}을 리턴합니다. 

코드

#include <string>
#include <vector>

using namespace std;

#define END 11

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

int get_score(vector<int> &a, vector<int> &r) {
    int apeach = 0, ryan = 0;
    for(int i=0; i<END; ++i) {
        if(a[i] == 0 && r[i] == 0) continue; // 둘 다 0점이면 패스
        
        if(a[i] >= r[i]) apeach += (10-i); // 어피치 >= 라이언이면 어피치가
        else ryan += (10-i); // 어피치 < 라이언이면 라이언이 점수 획득
    }
    
    if(ryan > apeach) return ryan - apeach;
    else return -1;
}

bool shoot_lower_score(vector<int> &ryan) {
    for(int i=END-1; i>=0; --i) { // 0점 과녁부터 비교
        if(ryan[i] > answer[i]) return true;
        else if(ryan[i] < answer[i]) return false;
    }
    return false;    
}

void func(vector<int> &apeach, vector<int> &ryan, int chance, int idx) {
    if(idx == END || chance == 0) {
        int score = get_score(apeach, ryan);
        if(score != -1) {
            /*
            	낮은 점수를 더 많이 맞힌 경우가 우선 순위가 있기 때문에,
                화살이 남아있으면 0점에 나머지 화살을 모두 쏨
            */
            if(chance > 0) ryan[idx-1] = chance; 
            
            if(score == max_score && shoot_lower_score(ryan)) {
                answer = ryan;
            }
            
            else if(score > max_score) {
                max_score = score;
                answer = ryan;
            }
            
            ryan[idx-1] = 0;
        }        
        return;
    }    
    
    if(chance > apeach[idx]) { // 어피치보다 한 발 더 맞추기
        ryan[idx] = apeach[idx] + 1;
        func(apeach, ryan, chance-ryan[idx], idx+1);
        ryan[idx] = 0;
    }
    
    func(apeach, ryan, chance, idx+1); // 쏘지 않고 다음 과녁으로
}

vector<int> solution(int n, vector<int> info) {
    vector<int> ryan(END, 0);
    
    func(info, ryan, n, 0);
    
    if(max_score == -1) return {-1};
    
    return answer;
}

실행 결과