[2022 KAKAO BLIND RECRUITMENT] 양궁대회 문제풀이

카카오 양궁대회 문제 풀이 링크
https://programmers.co.kr/learn/courses/30/lessons/92342

이 문제는 여러 방법으로 풀 수 있지만, 가장 대표적으로 떠오른 DFS 방법으로 풀어보았다.
가장 변수라고 생각되는 것이 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요. 부분인 것 같은데, 실제로 이 부분 때문에 테스트케이스 2개가 자꾸 안맞았다(테스트케이스 8번, 18번).

10점에서 0점으로 DFS돌면서 확인하는 방법으로 풀면, 점수 계산할 때 가장 낮은 점수를 더 많이 맞힌 경우를 해결하기 까다로웠다. diff >= point 조건처럼 =를 추가하면 동시에 낮은 점수도 함께 고려될 것이라 생각했는데, 가장 낮은 점수를 "더 많이" 맞혀야 하므로 뭔가 놓치고 있다는 생각이 들었다. (사실 아직도 반례를 찾지 못하였다...)

0점에서 10점으로 DFS돌면서, 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

#백트래킹 #카카오 #파이썬

중복조합은 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)