[완전탐색] 양궁대회 - 2022 KAKAO BLIND RECRUITMENT

해결 방법

화살을 쏴서 얻을 수 있는 점수로는 총 11가지(0점부터 10점) 경우가 있기 때문에, n개의 화살이 11가지 경우에 분배되는 모든 경우를 따지면 된다. 과녁에 있는 하나의 원에 여러 화살이 꽂힐 수도 있으므로 중복 조합(H)을 구하면 된다. 예를 들어, 입출력 예 #1 에서는 11H5=3003 가지 경우를 따지면 된다.

 

중복 조합을 구하는 소스 코드는 https://hydroponicglass.tistory.com/20를 참고했다.

 

중복 조합으로 계산한 모든 경우에 대해 어피치와의 점수 차이를 구하고 문제에 안내된 대로 동일 점수에 대한 처리도 진행해주면 된다.

 

 

소스 코드

#include <string>
#include <string.h>
#include <vector>
using namespace std;

vector<vector<string> > perm; // 중복 조합 저장
int result[11]; // 라이언의 결과

// 중복 조합 메소드 참고 : https://hydroponicglass.tistory.com/20
void repeated_combination(vector<string> v, vector<string> tmp, int r, int idx, int depth) {
    if(r==0) {
        perm.push_back(tmp);
        return;
    }
    else if(depth==v.size())
        return;
    else {
        tmp[idx]=v[depth];
        repeated_combination(v, tmp, r-1, idx+1, depth); // v[depth] 선택
        repeated_combination(v, tmp, r, idx, depth+1); // v[depth] 미선택
    }
}

// 점수 차이 계산
int get_relative_score(vector<int> apeach, int lion[]) {
    int apeach_score=0;
    int lion_score=0;
    for(int i=0;i<11;i++) {
        if(!apeach[i]&&!lion[i]) continue;
        if(apeach[i]>=lion[i]) apeach_score+=10-i;
        else lion_score+=10-i;
    }
    return lion_score-apeach_score;
}


vector<int> solution(int n, vector<int> info) {
    vector<int> answer;
    vector<string> tmp(n); // 각 조합의 결과
    vector<string> v; // 모든 원소("0"~"10")를 저장할 벡터
    bool new_record; // 기록 갱신 여부
    int maxi=0;
    int relative_score=0;
    
    for(int i=0;i<11;i++) answer.push_back(0); // answer 벡터를 모두 0으로 채워두기
    for(int i=0;i<11;i++) v.push_back(to_string(i)); // 모든 원소("0"~"10")를 저장
    
    repeated_combination(v, tmp, n, 0, 0); // 중복 조합 저장
    
    for(int i=0;i<perm.size();i++) {
        new_record=false;
        memset(result, 0, sizeof(result));
        for(int j=0;j<perm[i].size();j++) result[10-stoi(perm[i][j])]++; // 중복 조합 결과 저장
        relative_score = get_relative_score(info, result); // 점수 차이 계산
        if(relative_score>maxi) new_record=true; // 점수 차이가 최댓값보다 크다면 무조건 갱신
        else if(relative_score==maxi) { // 점수 차이가 최댓값이랑 동일한 경우
            for(int j=10;j>=0;j--) {
                if(result[j]==answer[j]) continue;
                else if(result[j]>answer[j]) new_record=true; // 가장 낮은 점수를 더 많이 맞힌 경우
                break;
            }
        }
        if(new_record) { // 기록 갱신
            maxi=relative_score;
            for(int k=0;k<11;k++) answer[k]=result[k];
        }
    }
    if(maxi<=0) {
        answer.clear();
        answer.push_back(-1);
    }
    return answer;
}

 

테스트케이스 25개 모두 정답

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/92342