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

코딩테스트 연습 - 양궁대회 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int N;
vector<int> apeach;
vector<int> lion;
vector<int> maxRes; // 정답 배열
int maxDiff = 0; // 최대 점수차

// (dpt : 깊이, asc : 현재 어피치 점수, lsc : 현재 라이언 점수, n : 현재 사용한 화살의 개수)
void dfs(int dpt, int asc, int lsc, int n){
    if(dpt==11) {
        if(lsc <= asc) return;//어피치가 이겼을 경우 return하여 -1 반환
        lion[10] += N-n; // 남은 화살 0점에 몰아주기
        if(lsc - asc > maxDiff) {//정답 배열 갱신
            maxRes = lion;
            maxDiff = lsc - asc;//최대 차이 갱신
        } else if(lsc - asc == maxDiff) { // 점수가 같은 경우, 낮은 점수에 많이 맞힌 경우가 정답
            for(int i=10; i>=0; i--){
                if(lion[i]==maxRes[i]) continue;
                else {
                    if(lion[i] > maxRes[i])
                        maxRes = lion;
                    break;
                }
            }
        }
        return;
    }
    // 라이언이 점수(10-dpt)를 획득하는 경우
    int next = apeach[dpt] + 1;
    if(n + next <= N) { // if문 만족할 경우
        int nasc = asc; // 다음 깊이에서의 어피치 점수
        int nlsc = lsc + 10 - dpt; // 다음 깊이에서의 라이언 점수(next+n, nasc, nlsc-> 축적되는 값)
        if(apeach[dpt]!=0) nasc -= (10-dpt);
        lion.push_back(next);
        dfs(dpt+1, nasc, nlsc, n + next);
        lion.pop_back(); // 백트래킹
    }
    lion.push_back(0);//기본실행문
    dfs(dpt+1, asc, lsc, n);//깊이만 갱신, 나머지는 갱신하지 않은 값 넣음
    lion.pop_back(); // 백트래킹
}

vector<int> solution(int n, vector<int> info) {
    N = n;
    apeach = info;
    int aSum = 0;
    for(int i=0; i<info.size(); i++){ if(info[i] > 0) {aSum += (10-i);}}//어피치 초기점수 세팅
    dfs(0, aSum, 0, 0);
    if(maxDiff==0) maxRes.push_back(-1);
    return maxRes;
}

많이 해도 아리까리한 그 녀석 .............. DFS...... 백트래킹을 해야한다면 더 나를 복잡하게 한다.

그치만 풀이법을 설명해보겠다.

 

1.어피치 초기 점수를 세팅한다.

0이 아닐 경우 더해가며 aSum을 구해준다.

 

 

2.기본으로 dfs가 실행될 경우 apeach[dpt] + 1 + n <= N라는 조건을 만족하지 않으면

단순히 lion에 0을 넣어주고 깊이만 증가시킨 채로 dfs실행 후 백트래킹을 위해 pop해준다.

if문에서 dfs문실행 이후에도 무조건적으로 실행되어야 함

 

3.apeach[dpt] + 1 + n <= N (기존 n으로부터 갱신된 현재 깊이의 apeach값 +1 이 N보다 작거나 같을 때)

라이언 점수는 증가시켜주고, 어피치 점수는 라이언 점수만큼 원래의 aSum에서 깎아서 갱신한다.

lion벡터에는 현재 apeach[dpt] + 1로 세팅된 값을 push해준다.

깊이, 참조할 어피치, 라이언의 점수, N까지 도달하게 될 n의 값을 모두 갱신해서 다음 dfs를 실행시킨다.

dfs실행이 끝났을 경우 backtracking을 위해 pop해준다.

 

dfs는 일반 절차지향문과 다르게 기본으로 실행되는 실행문은 if문 없이 그냥 쓰고 특정한 조건에 들어갈 때만 if문에 넣어서 써준다. 이 경우는 특별한 경우이므로