[프로그래머스] 2022 카카오 공채 양궁대회 C++ 풀이

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

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

 

2022 KAKAO BLIND RECRUITMENT 양궁대회 문제 C++ 풀이입니다.

 

 

필요한 배경지식

• DFS, 백트래킹, 조합론

 

문제 해결 방법

문제를 풀면서 고려해야할 사항들이 많지만, 기본적으로 k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져가는 게 아니라 k점만 가져가는 것 그리고 상대보다 한개라도 많이 맞추어야 점수를 획득할 수 있다는 점에 유의해야 한다.

 

해당 조건을 잘 생각해보면,

라이언이 11개의 점수를 각각 획득할지 안할지만 결정하면 되는 간단한 문제로 바꾸어 생각해 볼 수 있다.

획득을 한다면 어피치보다 1개의 화살을 더 맞추면 되고 그렇지 않으면 화살을 맞추지 않아도 되는 것이다.

이는 총 $2^{11}$ 의 가짓수만 고려하면 되므로, DFS를 이용하여 충분히 시간안에 풀어낼 수 있는 풀이이다.

 

이외에 생각해볼 조건으로,

1. 어피치가 하나라도 맞춘 점수에 라이언이 더 많이 맞출 경우, DFS과정에서 어피치와 라이언의 점수가 모두 바뀌어 점수차에도 변동이 생기기 때문에 주의해 주어야 한다.

2. 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우가 정답이 되므로 화살이 남아있는 경우 0점에 모두 맞추는 것으로 처리해 주어야 한다.

3. 라이언이 어떠한 방법으로도 어피치보다 점수가 높지 못하면 -1을 출력해 주어야 한다.

 

 

 

 

C++ 코드

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

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

// dpt : 깊이, (10-dpt)가 점수가 됨
// asc : 현재 어피치 점수
// lsc : 현재 라이언 점수
// n : 현재 사용한 화살의 개수
void dfs(int dpt, int asc, int lsc, int n){
    if(dpt==11) {
        if(lsc <= asc) return;
        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(next + n <= N) { // 화살 최대 개수를 넘기면 안됨
        int nasc = asc; // 다음 깊이에서의 어피치 점수
        int nlsc = lsc + 10 - dpt; // 다음 깊이에서의 라이언 점수
        if(next!=1) nasc -= (10-dpt);
        lion.push_back(next);
        dfs(dpt+1, nasc, nlsc, next+n);
        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 total = 0; // 어피치의 초기 점수
    for(int i=0; i<info.size(); i++){
        if(info[i]) {
            total += (10-i);
        }
    }
    
    dfs(0, total, 0, 0);
    
    // maxDiff가 0인 경우 업데이트가 되지 않았으므로 어떠한 방법으로도 어피치의 점수를 넘길 수 없음
    if(maxDiff==0) maxRes.push_back(-1);
    return maxRes;
}