Programmers : 양궁대회

풀이 요약

완전탐색 DFS.

풀이 상세

1. 라이언이 어피치보다 점수를 얻는 경우를 생각해보자.

   • 조건 1: 라이언이 어피치 보다 $k$ 점에 더 많이 화살을 맞춘 경우, $k$ 점을 획득한다.

     • 라이언은 어피치의 점수로 부터, $k$ 점을 뺏는 결과가 발생한다.

   • 조건 2: 어피치가 한 개도 못 맞춘 $k$ 점에 대해 하나라도 맞추면, $k$ 점을 획득한다.

     • 라이언은 점수를 얻으나, 어피치가 점수가 깎이는 것은 아니다.

2. 예외도 존재한다.

   • 조건 1: 마지막 인덱스 $0$ 점까지 탐색까지 화살갯수가 남았으나, 어떤 조합으로도 $0$ 점에 남은 화살을 할당하는 것과 동일한 결과가 나오는 경우,

     • $0$ 점은 라이언이 많이 맞추든, 어피치가 많이 맞추든 점수 획득도, 점수가 깎이는 것도 없다. 만약 […,1,1,1] 과 […0,0,3] 이 서로 동일한 최대 차이를 가져온다면, 낮은 점수를 더 많이 맞추는 경우 때문에 […0,0,3] 쪽이 정답이 된다.

3. 최대 차이를 나타내는 경우는 여러개가 나타날 수 있다. 만약 업데이트 된 최대 차이값이 한번 더 나타나는 경우에는 이전 벡터와 현재 백터를 비교하여 누가 더 낮은 점수를 많이 맞추었는지 비교해야 한다.

배운점

1. c++ 에는 벡터 혹은 배열 복사에 용이한 memcpy 라는 함수가 있다.

#include <vector>
#include <cstring>

using namespace std;
vector<int> temp = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
vector<int> answer = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int diff = 0;

bool check() {
    for (int i = 10; i >= 0; i--) {
        if (temp[i] > answer[i]) return true;
        else if (temp[i] < answer[i]) return false;
    }
    return true;
}

void dfs(int n, vector<int> &info, int idx, int sum, int cnt, int ap_sum) {
    if (n < cnt) return;
    else if (n == cnt) {
        if (sum > ap_sum) {
            if (diff <= sum - ap_sum) {
                if (diff == sum - ap_sum && !check()) return;
                diff = sum - ap_sum;
                memcpy(&answer[0], &temp[0], sizeof(temp[0]) * answer.size());
            }
        }
        return;
    }

    for (int i = idx; i < info.size(); i++) {
        temp[i] = info[i] + 1;
        if (info[i] == 0) {
            dfs(n, info, i + 1, sum + 10 - i, cnt + temp[i], ap_sum);
        } else {
            if (i == 10 && n > cnt) {
                temp[i] = n - cnt;
                dfs(n, info, i + 1, sum, n, ap_sum);
            } else {
                dfs(n, info, i + 1, sum + 10 - i, cnt + temp[i], ap_sum - (10 - i));
            }
        }
        temp[i] = 0;
    }
}

vector<int> solution(int n, vector<int> info) {
    int ap_sum = 0;
    for (int i = 0; i < info.size(); i++) {
        if (info[i] > 0) {
            ap_sum += 10 - i;
        }
    }
    dfs(n, info, 0, 0, 0, ap_sum);
    if (diff == 0) return {-1};
    return answer;
}