[PCCP] Lv2: 양궁대회(92342) 해설

문제

- 문제 링크: 양궁대회

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

 

(C++)

solution 1)

- 0-10점 각 과녁에 화살을 맞힌다/못 맞힌다 두 상태가 있으므로 시간복잡도는 O(2^11)

#include <vector>

using namespace std;

vector<int> answer;
vector<int> ryan(11, 0);
int maxScore = -1;

// 어피치와 라이언의 점수 차이 계산
int calcScoreDiff(const vector<int> &apeach) {
    int scoreApeach = 0;
    int scoreLion = 0;
    
    for (int i = 0; i < 11; ++i) {
        if (apeach[i] == 0 && ryan[i] == 0)
            continue;
        if (apeach[i] >= ryan[i])
            scoreApeach += 10 - i;
        else
            scoreLion += 10 - i;
    }
    
    return scoreLion - scoreApeach;
}

void dfs(const vector<int> apeach, int score, int arrow) {
    if (score == -1 || arrow == 0) {
        ryan[10] = arrow;
        int scoreDiff = calcScoreDiff(apeach);
        // 현재 구한 점수 차가 기존 최대 점수 차보다 더 크고, 라이언의 점수가 더 높으면 갱신
        if (scoreDiff > 0 && maxScore < scoreDiff) {
            maxScore = scoreDiff;
            answer = ryan;
        }
        ryan[10] = 0;
        return;
    }
    
    // 아직 어피치가 쏠 화살이 남은 경우
    if (arrow > apeach[score]) {
        ryan[score] = apeach[score] + 1;
        dfs(apeach, score - 1, arrow - apeach[score] - 1);
        ryan[score] = 0;
    }
    
    // 어피치가 화살을 사용하지 않는 경우
    dfs(apeach, score - 1, arrow);
}

vector<int> solution(int n, vector<int> info) {
    // 10점 과녁부터 모든 조합을 확인
    dfs(info, 10, n);
    
    // 라이언이 이길 수 없는 경우
    if (maxScore == -1)
        answer.push_back(-1);
    
    return answer;
}

solution 2)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

 

(Java)

solution 1)

- 0-10점 각 과녁에 화살을 맞춘다/못 맞춘다 두 상태가 있으므로 시간복잡도는 O(2^11)

class Solution {
    private static int max;
    private static int[] answer;
    private static int[] apeach;
    
    // 주어진 조합에서 각각의 점수 계산
    private static int getScore(int[] ryan) {
        int score = 0;
        for (int i = 0; i <= 10; ++i) {
            if (ryan[i] + apeach[i] > 0) {
                score += ryan[i] > apeach[i] ? (10 - i) : -(10 - i); 
            }
        }
        return score;
    }
    
    // 최대 차이와 라이언의 과녁 저장
    private static void calculateDiff(int[] ryan) {
        int score = getScore(ryan);
        if (max < score) {
            max = score;
            answer = ryan.clone();
        }
        // 점수가 같으면 가장 낮은 점수를 더 많이 맞힌 경우를 찾음
        else if (max > 0 && max == score) {
            for (int i = 10; i >= 0; --i) {
                if (answer[i] != ryan[i]) {
                    if (answer [i] < ryan[i]) {
                        answer = ryan.clone();
                    }
                    break;
                }
            }
        }
    }
    
    // 가능한 라이언의 과녁 점수 조합의 모든 경우를 구함
    private static void backtrack(int n, int idx, int[] ryan) {
        if (n == 0) {
            calculateDiff(ryan);
            return;
        }
        
        for (int i = idx; i <= 10; ++i) {
            int cnt = Math.min(n, apeach[i] + 1);
            ryan[i] = cnt;
            backtrack(n - cnt, i + 1, ryan);
            ryan[i] = 0;
        }
    }
    
    
    public static int[] solution(int n, int[] info) {
        apeach = info;
        max = 0;
        backtrack(n, 0, new int[11]);
        // 최대 차이가 0인 경우 -1 반환, 아니면 answer 반환
        return max == 0 ? new int[]{-1} : answer;
    }
}

solution 2)

#include<>

 

(Python)

solution 1)

- 0-10점 각 과녁에 화살을 맞춘다/못맞춘다 두 가지 상태이므로 O(2^11)

from itertools import combinations_with_replacement
from collections import Counter

def solution(n, info):
    maxdiff, max_comb = 0, {}
    
    # 주어진 조합에서 각각의 점수 계산
    def calculate_score(combi):
        score1, score2 = 0, 0
        for i in range(1, 11):
            if info[10 - i] < combi.count(i):
                score1 += i
            elif info[10 - i] > 0:
                score2 += i
        return score1, score2
    
    # 최대 차이와 조합 저장
    def calculate_diff(diff, cnt):
        nonlocal maxdiff, max_comb
        if diff > maxdiff:
            max_comb = cnt
            maxdiff = diff
    
    # 가능한 라이언의 과녁 점수 조합의 모든 경우에 대해서 체크
    for combi in combinations_with_replacement(range(11), n):
        cnt = Counter(combi)
        score1, score2 = calculate_score(combi)
        diff = score1 - score2
        calculate_diff(diff, cnt)
    
    # 최대 차이가 0 이상인 경우, 조합 반환
    if maxdiff > 0:
        answer = [0] * 11
        for n in max_comb:
            answer[10 - n] = max_comb[n]
        return answer
    else: # 최대 차이가 0인 경우, -1 반환
        return [-1]

solution 2)

import

 

(JavaScript)

solution 1)

- 각 과녁에 화살을 맞힌다/못 맞힌다 두 상태가 있으므로 시간복잡도: O(2^11)

function combinationsWithRepetition(arr, n) {
    if (n === 1)
        return arr.map((v) => [v]);
        
    const result = [];
    arr.forEach((fixed, idx, arr) => {
        const rest = arr.slice(idx);
        const combis = combinationsWithRepetition(rest, n - 1);
        const combine = combis.map((v) => [fixed, ...v]);
        result.push(...combine);
    });
    
    return result;
}

function solution(n, info) {
    let maxdiff = 0;
    let maxComb = {};
    
    // 주어진 조합에서 각각의 점수 계산
    function calculateScore(combi) {
        let score1 = 0;
        let score2 = 0;
        for (let i = 1; i <= 10; ++i) {
            if (info[10 - i] < combi.filter((x) => x === i).length) {
                score1 += i;
            } else if (info[10 - i] > 0) {
                score2 += i;
            }
        }
        return [score1, score2];
    }
    
    // 최대 차이와 조합 저장
    function calculateDiff(diff, cnt) {
        if (diff > maxdiff) {
            maxComb = {...cnt};
            maxdiff = diff;
        }
    }
    
    // 가능한 라이언의 과녁점수 조합의 모든 경우에 대해서 체크
    for (const combi of combinationsWithRepetition([...Array(11).keys()], n)) {
        const cnt = combi.reduce((acc, cur) => {
            acc[cur] = (acc[cur] || 0) + 1;
            return acc;
        }, {});
        
        const [score1, score2] = calculateScore(combi);
        const diff = score1 - score2;
        calculateDiff(diff, cnt);
    }
    
    // 최대 차이가 0 초과인 경우, 조합 반환
    if (maxdiff > 0) {
        const answer = Array(11).fill(0);
        for (const n of Object.keys(maxComb)) {
            answer[10 - n] = maxComb[n];
        }
        return answer;
    } else {
        // 최대 차이가 0 초과인 경우, -1 반환
        return [-1];
    }
}

solution 2)

import