[Programmers] 2022 KAKAO BLIND 양궁대회 (C++)

문제 설명

---

제한사항

 

보자마자 dfs를 사용해야 겠다는 생각이 들었다. dfs 를 기저로 깔고, 추가 유의 사항들을 정리해 보았다

• 라이언 > 어피치 인 경우에만 라이언이 점수를 얻는다 (라이언 = 어피치 or 어피치 > 라이언 인경우 어피치가 점수를 얻는다)
• 가장 큰 점수차이를 낼 수 있는 방법이 여러가지일 경우 가장 낮은 점수를 더 많이 맞힌 경우
• info 배열은 고정크기 11 이다

처음에 dfs 를 구현할 때, 단순히 각 자리에 1씩 추가하며 재귀함수를 도는 방식으로 구현하였다. 

그러다 그냥 한번에 어피치가 쏜 화살 개수 + 1 개를 한번에 계산하면 된다는 것을 깨달았다.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int ans = 0;
vector<int> answer = {-1};

void create(vector<int> info, vector<int> ryan, int n, int sum, int idx){

    if(sum == n){
        int res = 0;
        for(int i = 0; i<11; i++){
            if(ryan[i] > info[i]){
                res += (10 - i);
            }else if(info[i]){
                res -= (10 - i);
            }
        }
        if(res > ans && res){
            ans = res;
            answer = ryan;
        }
        else if(res == ans && res){
            for(int i = 10; i >= 0; i--){
                if(answer[i] > ryan[i]) return;
                else if(answer[i] < ryan[i]){
                    answer = ryan;
                    break;
                }
            }
        }
        return;
    }
    for(int i = idx; i < info.size(); i++){
        int num = info[i] + 1;
        if(num > n - sum) num = n - sum;
        ryan[i] = num;
        create(info, ryan, n, sum + num, i + 1);
        ryan[i] = 0;
    }

}

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

    vector<int> ryan(info.size(),0);
    create(info, ryan, n, 0, 0);
    return answer;
}