프로그래머스 양궁대회 C++

 

라이언이 점수를 획득하려면 어피치가 쏜 것보다 무조건 하나이상 더 쏴야한다.

나는 그 점을 생각하여 풀었다.

 

근데 추천 수를 가장 많이 받은 다른 사람의 풀이를 확인해보니, 그냥 N 발을 전체 다 하나씩 탐색하는 경우로 푸셨다.

아마 내 풀이보다는 오래 걸릴 것으로 생각된다..!!

#include <string>
#include <vector>

using namespace std;

vector<int> lions(11, 0); // lion의 과녁
vector<int> ans;

int maxGap;

// shot : 남은 발 수
void dfs(int n, vector<int>& info, int index, int shot, int scoreLion, int scoreAppeach) {
    
    if(index < 0) {
        
        int gap = scoreLion - scoreAppeach;
        
        if(maxGap < gap) {
            maxGap = gap;
            ans = lions;
            
            if(shot > 0) // 남은 발 수가 있으면 0점에 채워넣음
                ans[10] = shot;
        }
        return;
    }
    
    // 맞추기
    if(shot >= (info[index] + 1)) {
        lions[index] = info[index] + 1;
        dfs(n, info, index - 1, (shot - (info[index] + 1)), scoreLion + (10 - index), scoreAppeach);
        lions[index] = 0;
    }

    // 안맞추고 넘기기
    if(info[index] > 0) {
        dfs(n, info, index - 1, shot, scoreLion, scoreAppeach + (10 - index));
    } else {
        dfs(n, info, index - 1, shot, scoreLion, scoreAppeach);
    }
    
}

vector<int> solution(int n, vector<int> info) {
    vector<int> answer;
    
    dfs(n, info, 9, n, 0, 0);
        
    if(ans.empty()) return {-1}; else return ans;
}