카카오 양궁대회 문제 풀이 링크
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)