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

문제 설명

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

---

풀이

60분 이상
쉽게 생각하고 접근했다가 꽤나 오래 걸렸다.(난이도가 Level2 라는 것도 방심하는데 한 몫 했다;;)
찾아내는데 가장 오래걸린 조건은

• 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.

였다. dfs로 순회를 하되, 지는 경우를 먼저 세면서 갱신하면 낮은 점수를 더 많이 맞힌 경우가 자연스럽게 갱신된다고 착각했었다. 사실 이 부분은 문제의 제한사항에서의 예시를 주의깊게 살펴봤다면 알아차릴 수 있었던 부분이다. 또,

int max_gap = 0;

위처럼 어피치와 라이언의 점수차의 최댓값을 갱신하면서 dfs를 진행했는데, 초기값이 0 이다 보니 반드시 비기는 경우에 [-1]을 리턴하지 못하는 예외가 있었다.

코드

// 03:10 ~ 04:10
#include <string>
#include <vector>
#include <iostream>

using namespace std;


vector<int> ans;
vector<int> to_win(11);
int max_gap = 0;
int n;

bool is_low_largest(vector<int> v){
    if(ans.empty()) return true;
    int ans_idx = -1, v_idx = -1;
    for(int i = 10; i >= 0; --i){
        if(ans_idx < 0 && ans[i] > 0) ans_idx = i;
        if(v_idx < 0 && v[i] > 0) v_idx = i;
    }
    if(v_idx > ans_idx) return true;
    if(v_idx == ans_idx && v[v_idx] > ans[ans_idx]) return true;
    return false;
}

void dfs(int idx, int sum , vector<int> v){
    if(idx == 10){
        v[10] = n - sum;
        sum = n;
    }
    if(sum == n){
        int apeach = 0, lion = 0;
        for(int i =0; i < 11; ++i){
            if(v[i] > 0) lion += (10 - i);
            else if(v[i] == 0 && to_win[i] > 1)apeach += (10 - i);
        }
        if(lion - apeach > max_gap || (max_gap > 0 && lion - apeach == max_gap && is_low_largest(v))){
            max_gap = lion - apeach;
            ans = v;
        }
        return;
    }

    // loose
    dfs(idx + 1, sum, v);
    
    // win
    if(n >= to_win[idx] + sum){
        v[idx] = to_win[idx];
        dfs(idx + 1, sum + to_win[idx], v);
    }

}

vector<int> solution(int _n, vector<int> info) {
    vector<int> v(11);
    n = _n;
    for(int i =0; i <= info.size(); ++i){
        to_win[i] = info[i] + 1;
    }
    dfs(0, 0, v);

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