lv2 / 양궁대회 / 카카오 / C++

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

프로그래머스

---

dfs를 통한 완전탐색 기법은 아직도 감을 잘 못잡겠다. 솔직히 완전탐색을 해야한다는 것만 알아채고, 딱히 뭘 더 할 수 없었다. 공부는 해도해도 부족하고 새로운 것 같다. 

 

dfs를 통해 화살을 적절히 배치해준다. 적절히 배치라는건 무슨 뜻일까? 양궁대회 운영진들은 라이언을 억까(?)하기 위해 규칙을 불리하게 만들었다. 그래서 어피치가 K점에 a개의 화살을 쐈다면, 라이언에게는 두가지의 선택지가 존재한다. K점을 얻거나, 얻지 않고 다른 점수를 얻거나. K점을 얻으려면 라이언은 a + 1개의 화살을 쏴야 한다. 왜 굳이 1개만 더 쏘는 걸까? 효율의 문제이다. a - 1이하의 화살을 사용하면, 점수는 점수대로 얻지도 못하고, 화살 가져다 버리는 꼴이 된다. a + 2 이상의 화살을 사용하면, a + 1개나, a + 5개나 어쨌든 K점만 얻기 때문이다. 어짜피 더 많이 맞춰도 얻는 점수가 같으면, 차라리 다른데에 쏴서 다른 점수도 얻어보는게 이득아니겠는가. 

 

그러면 둘중 뭐가 더 이득일까? 답은 알수 없다. K점을 얻는 경우와, 얻지 않는 경우 모두 탐색해봐야 한다.

 

그래서 필자는 먼저 K점을 얻어보고 다음 배치를 진행한다. 이렇게 해서 탐색을 끝내면, K점에 배치를 했을 경우를 모두 살폈기 때문에, 돌아와서는 다시 0개를 배치하고, 그 이후 또 탐색을 하여, 어떤 경우가 최대 점수차이를 낼 수 있는가를 따졌다.

 

아래는 내가 겪은 테스트케이스 오류들이다.

• 점수차이가 동일한 경우, 가장 낮은 점수에 화살을 더 많이 쏜 쪽으로 정답을 내야한다(테스트케이스8, 18)
• 라이언과 어피치가 비기는 경우가 존재한다. 이 역시 이길수 없는 것이기 때문에 -1을 리턴해야한다. 이거 때문에 계속 코드 고치고 있었다. (TC 23)

 

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

int max_diff = -1;
vector<int> ryan(11, 0), apeach, result;

pair<int, int> get_score() {
    pair<int, int> score = {0, 0}; // {ryan, apeach}
    for(int i = 0; i < 11; i++) { 
        if(ryan[i] == apeach[i]) {
            if (ryan[i] == 0) continue;
            else score.second += 10 - i;
        }
        else {
            if (ryan[i] > apeach[i]) score.first += 10 - i;
            else score.second += 10 - i;
        }
    }
    return score;
}

void check() {
    pair<int, int> score = get_score();
    int ryan_score = score.first;
    int apeach_score = score.second;
    int diff = ryan_score - apeach_score;
    
    if (diff < 0 || max_diff > diff) return; // ryan이 apeach보다 점수를 적게 받았거나, 최대 점수차이가 아니면 답이 아니다.
    
    if (max_diff < diff) {
        max_diff = diff;
        result = ryan;
    }
    else if(max_diff == diff) { // 점수차이가 같다면, 더 낮은 점수를 더 많이 맞춘 경우로 답을 바꾼다.
        for(int i = 10; i >= 0; i--) {
            if (ryan[i] > result[i]) {
                result = ryan;
                break;
            }
            else if (ryan[i] < result[i]) {
                break;
            }
        }
    }
}

void dfs(int cnt, int idx, int n) { // 화살 배치
    if (cnt == n) {
        check();
        return;
    }
 
    int curArrow = n - cnt;
    if (idx == 10) {    
        ryan[idx] = curArrow;
        dfs(cnt + curArrow, idx + 1, n);
        ryan[idx] = 0;
    } else {
        if (apeach[idx] + 1 <= curArrow) {
            ryan[idx] = apeach[idx] + 1;
            dfs(cnt + apeach[idx] + 1, idx + 1, n);
            ryan[idx] = 0;
        }
        dfs(cnt, idx + 1, n);
    }
}

vector<int> solution(int n, vector<int> info) {
    apeach = info;
    dfs(0, 0, n);

    if (max_diff == -1) result.push_back(-1);
    else if (max_diff == 0) {
        result.clear();
        result.push_back(-1);
    }
    return result;
}

 

 

코드 참조

• https://yabmoons.tistory.com/726