Programming프로그래머스경우의 수중복 순열

프로그래머스 - 양궁 대회 (Cpp)

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

유의 사항

  • 화살을 맞춘 개수를 저장하고 정렬하는데 있어서 주의해야 한다.
  • 정렬에 대한 가중치가 앞자리가 아닌 뒷자리 에 있으므로 값을 저장할 때 뒤집어서 저장한 후
  • 내림 차순으로 정렬해 가장 큰 값을 가져와 해당 값을 뒤집으면 가장 낮은 점수를 많이 맞춘 순서대로 정렬된 값을 가져올 수 있다.
#include <bits/stdc++.h>
using namespace std;

int max_diff = -1;
vector<string> scores;

int getValue(int idx) {
    return 10 - idx;
}

void calScore(vector<int> apeach, vector<int> ryan) {
    int diff = 0;
    int total_apeach = 0;
    int total_ryan = 0;
    for (int i = 0; i < 11; i++) {
        if (apeach[i] == 0 && ryan[i] == 0) {
            continue;
        }

        if (apeach[i] >= ryan[i]) {
            total_apeach += getValue(i);
        } else {
            total_ryan += getValue(i);
        }
    }

    if (total_ryan > total_apeach) {
        diff = total_ryan - total_apeach;
    } else {
        return;
    }

    string str;
    for (int i : ryan) {
        str += i + '0';
    }
    reverse(str.begin(), str.end());

    if (diff > max_diff) {
        max_diff = diff;
        scores.clear();
        scores.push_back(str);
    } else if (diff == max_diff) {
        scores.push_back(str);
    }
}

void back_tracking(int depth, int idx, int n, vector<int>& apeach, vector<int>& ryan) {
    if (idx > 10) {
        return;
    }

    if (depth == n) {
        calScore(apeach, ryan);
        return;
    }

    ryan[idx] += 1;
    back_tracking(depth + 1, idx, n, apeach, ryan);
    ryan[idx] -= 1;
    back_tracking(depth, idx + 1, n, apeach, ryan);
}

vector<int> solution(int n, vector<int> info) {
    vector<int> answer;
    vector<int> ryan = vector<int>(11, 0);
    back_tracking(0, 0, n, info, ryan);

    if (max_diff == -1) {
        answer.push_back(-1);
    } else {
        sort(scores.begin(), scores.end(), greater<string>());
        string str = scores[0];
        reverse(str.begin(), str.end());
        for (int i = 0; i < str.size(); i++) {
            answer.push_back(str[i] - '0');
        }
    }
    return answer;
}
Share