[2022 KAKAO BLIND RECRUITMENT]アーチェリー競技解答

Kakaoアーチェリー大会解答リンク
https://programmers.co.kr/learn/courses/30/lessons/92342

この問題は種々の方法で解決できるが,最も代表的なDFS法で解決した.
最変数が最低点数だと思ったら、もっと多くの点数を返してください.一部のようですが、実際にはこの部分のため、2つのテストケースはいつも間違っています(テストケース8番、18番).
10分から0分にDFSを回して確認する方法で解くと、点数を計算するときに最低の点数が正解する回数が多くなる場合は解決しにくいです.diff>=point条件のように=を追加すると、低い点数も同時に考えられますが、最低点数は「もっと」正解が必要なので、何か見逃したような気がします.(実はまだ反例は見つかっていません…)
0点からDFSを10点に回し、diff>point条件で点数を確認するとパスします.
空っぽな感じがする.2級の時に多くの時間を費やした問題ㅠㅠ
DFSアルゴリズムの説明:https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ndb796&logNo=221230945092

def calcPoint(apeach, lion):
    apeach_score = 0
    lion_score = 0
    for i in range(11):
        if apeach[i] == lion[i] == 0:
            continue
        if apeach[i] >= lion[i]:
            apeach_score += 10 - i
        else:
            lion_score += 10 - i
    return lion_score - apeach_score

# 지금쏘는 과녁 idx, 남은 화살 개수, 어피치점수, 내점수
def DFS(idx, n, apeach, lion):
    global answer, point
    if n < 0:
        return
    #점수 계산
    if idx > 10:
        diff = calcPoint(apeach, lion)
        if diff <= 0:
            return
        if diff > point:
            point = diff
            answer = [lion[i] for i in range(11)]
            answer[10] += n            
        return

    #상대가 쏜 점수보다 높이 쏴본다
    lion[10-idx] = apeach[10-idx]+1
    DFS(idx+1, n-lion[10-idx], apeach, lion)
    lion[10-idx] = 0
    DFS(idx+1, n, apeach, lion)

def solution(n, info):
    global answer, point
    answer = [-1]
    point = 0
    DFS(0, n, info, [0 for _ in range(11)])
    return answer

#後追跡#Kakao#FiSun
繰り返しの組み合わせはpythonで実現されます.itertoolsを使用すると、並べ替え、組み合わせ、繰り返しの組み合わせが簡単に行えます.
しかし、DFSよりも時間がかかる方法は、すべての場合に試してみなければならない.
この方式も0点から10点まで順番に点数を計算してから正確に計算するので注意しましょう.

from itertools import combinations_with_replacement as combis
from collections import Counter

def combination(n, info):
    global answer, max_point
    # 0 ~ 11까지 n개 중복조합 뽑기 ex.(1, 1, 1, 1, 1)
    for combi in combis(range(11), n):
        #Counter를 통해 각 원소의 개수 구하기 ex.Counter({1: 5})
        cnt = Counter(combi)
        apeach, lion = 0, 0
        #점수계산
        for i in range(11):
            if info[10-i] < cnt[i]:
                lion += i
            elif info[10-i] > 0:
                apeach += i
        if lion-apeach > max_point:
            max_point = lion-apeach
            for i in range(11):
                answer[10-i] = cnt[i] 

def solution(n, info):
    global answer, max_point
    answer = [0]*11
    max_point = 0
    combination(n, info)
    if max_point == 0:
        answer = [-1]
    return answer

参照)
DFS

테스트 1 〉	통과 (0.16ms, 10.3MB)
테스트 2 〉	통과 (2.24ms, 10.3MB)
테스트 3 〉	통과 (2.09ms, 10.3MB)
테스트 4 〉	통과 (1.64ms, 10.2MB)
테스트 5 〉	통과 (2.41ms, 10.3MB)
테스트 6 〉	통과 (4.19ms, 10.3MB)
테스트 7 〉	통과 (0.91ms, 10.2MB)
테스트 8 〉	통과 (0.64ms, 10.3MB)
테스트 9 〉	통과 (1.32ms, 10.3MB)
테스트 10 〉	통과 (0.35ms, 10.3MB)
테스트 11 〉	통과 (0.56ms, 10.2MB)
테스트 12 〉	통과 (0.82ms, 10.3MB)
테스트 13 〉	통과 (1.60ms, 10.2MB)
테스트 14 〉	통과 (2.13ms, 10.2MB)
테스트 15 〉	통과 (2.32ms, 10.3MB)
테스트 16 〉	통과 (1.20ms, 10.2MB)
테스트 17 〉	통과 (0.87ms, 10.2MB)
테스트 18 〉	통과 (0.15ms, 10.2MB)
테스트 19 〉	통과 (0.05ms, 10.3MB)
테스트 20 〉	통과 (2.07ms, 10.2MB)
테스트 21 〉	통과 (2.12ms, 10.3MB)
테스트 22 〉	통과 (2.39ms, 10.3MB)
테스트 23 〉	통과 (0.67ms, 10.2MB)
테스트 24 〉	통과 (2.26ms, 10.4MB)
테스트 25 〉	통과 (3.40ms, 10.3MB)

くりかえしくみたて

테스트 1 〉	통과 (0.26ms, 10.3MB)
테스트 2 〉	통과 (326.53ms, 10.3MB)
테스트 3 〉	통과 (337.32ms, 10.2MB)
테스트 4 〉	통과 (10.38ms, 10.2MB)
테스트 5 〉	통과 (676.04ms, 10.2MB)
테스트 6 〉	통과 (684.01ms, 10.3MB)
테스트 7 〉	통과 (10.52ms, 10.2MB)
테스트 8 〉	통과 (1.05ms, 10.3MB)
테스트 9 〉	통과 (10.54ms, 10.2MB)
테스트 10 〉	통과 (1.09ms, 10.1MB)
테스트 11 〉	통과 (3.53ms, 10.2MB)
테스트 12 〉	통과 (3.55ms, 10.2MB)
테스트 13 〉	통과 (67.35ms, 10.2MB)
테스트 14 〉	통과 (366.51ms, 10.2MB)
테스트 15 〉	통과 (371.82ms, 10.2MB)
테스트 16 〉	통과 (28.93ms, 10.3MB)
테스트 17 〉	통과 (11.19ms, 10.3MB)
테스트 18 〉	통과 (0.27ms, 10.4MB)
테스트 19 〉	통과 (0.07ms, 10.2MB)
테스트 20 〉	통과 (377.07ms, 10.3MB)
테스트 21 〉	통과 (380.21ms, 10.3MB)
테스트 22 〉	통과 (796.91ms, 10.2MB)
테스트 23 〉	통과 (1.02ms, 10.2MB)
테스트 24 〉	통과 (648.74ms, 10.2MB)
테스트 25 〉	통과 (646.38ms, 10.3MB)