[프로그래머스][level2] 양궁대회 (C++)

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

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

 

[난이도] level2
[유형] 백트래킹

[풀이]
라이언이 N개의 화살을 각 과녁에 쏠 수 있는 모든 경우의 수를 백트래킹으로 구해주면 됩니다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
vector<int> info,ans;
int ansv=-1,n;
void cmp(vector<int> v){
    int a=0,b=0;
    for(int i=0;i<=10;i++){
        if(info[i]==0&&v[i]==0) continue;
        if(info[i]>=v[i]){
            a+=10-i;
        }else{
            b+=10-i;
        }
    }
    if(b>a){
        if(ansv<b-a){
            ansv=b-a;
            ans=v;
        }else if(ansv==b-a){
            vector<int> rans=ans,rv=v;
            reverse(rans.begin(),rans.end());
            reverse(rv.begin(),rv.end());
            if(rv>=rans){
                ans=v;
            }
        }
    }
}
void sol(int m,int cur,vector<int> v){
    if(m==11){
        if(cur!=0) return;
        cmp(v);
        return;
    }
    for(int i=0;i<=cur;i++){
        v.push_back(i);
        sol(m+1,cur-i,v);
        v.pop_back();
    }
}
vector<int> solution(int _n, vector<int> _info) {
    info=_info;
    n=_n;
    sol(0,n,{});
    if(ansv==-1) ans={-1};
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/양궁대회.cpp