이 문제를 3가지 방식으로 풀었는데, 각각의 방법 모두 좋은 것 같아 3가지 방법으로 풀어보았다.
문제에 접근할때 생각은 n개를 쏘는데, 10부터 0점중에 n개를 어떻게 나열할까라고 생각했다. 그렇기 때문에 0부터 10까지 숫자중에 중복하여 n개의 숫자를 뽑고 모든 경우의 수를 탐색하여 최적의 해를 찾는 방향으로 풀이를 잡았다.
- 브루트포스
말그대로 파이썬 중복조합 라이브러리인 combinations_with_replacement를 이용해 조합을 구하고, 어피치와 라이언의 점수표를 비교해 점수차가 기존 점수차보다 크면 갱신하고, 아니면 넘기는 방식으로 구현했다.
from itertools import combinations_with_replacement
def compare(a,b):
apeche = 0
lion = 0
for i in range(11):
if a[i] == 0 and b[i] == 0:
continue
elif a[i] >= b[i]:
apeche += 10 - i
else:
lion += 10 - i
return apeche,lion
def solution(n, info):
score_diff = 0
possible = []
combination = combinations_with_replacement(range(11),n)
for comb in combination:
lion = [0]*11
for c in comb:
lion[c] += 1
apeche_score,lion_score = compare(info,lion)
if lion_score - apeche_score > score_diff:
del possible[:]
possible.append(lion)
score_diff = lion_score - apeche_score
elif lion_score - apeche_score == score_diff and score_diff != 0:
possible.append(lion)
# 배열 원소 순으로 정렬
if len(possible) == 0:
return [-1]
for i in range(len(possible)):
possible[i].reverse()
possible.sort(reverse = True)
possible[0].reverse()
return possible[0]- 그리디 + 비트마스크
이 문제는 그리디로도 풀이가 가능한데, 라이언 입장에서 최대한 점수차를 벌리기 위해서는 어떻게 해야할까라고 생각했다. 생각해보면, 어피치가 적중한 개수보다 한개가 많든 두개가 많든 같은 점수를 얻는다는 것이다.
그렇기 때문에 라이언은 어떤 점수 i에 대하여 i점을 받거나 0점을 받거나 두가지 경우밖에 없는 것이다.
문제 해결을 위해서는 라이언이 맞춘 개수의 배열을 생각하기 보단, 라이언이 어느 점수에서 이길 수 있을가를 생각하면 된다.
예를 들어 라이언이 10,9,8점에서만 점수를 가져간다면, [1110000000]이 되고, 이를 비트마스크를 이용해 10개의 비트수의 경우의수 1024개를 순회하면서, 비트마스크와 &연산을 통해 이긴곳의 점수만 반영해주고, 라이언이 맞춘 화살의 갯수는 어피치가 맞춘 화살의 갯수 + 1로 적을 수 있다.
def compare(a, b):
return a[::-1] > b[::-1]
def solution(n, info):
ans = [-1] * 12
for lionbit in range(1024): ##
lion = [0] * 12
ascore = 0
lscore = 0
cnt = n
for maskbit in range(10):
x = lionbit & (1 << maskbit)
if x: ## 비트가 켜져 있다면 라이언이 이겨야 하는 경우
lscore += 10 - maskbit
lion[maskbit] = info[maskbit] + 1
cnt -= lion[maskbit]
elif info[maskbit] != 0: ## 어피치가 이기는 경우
ascore += 10 - maskbit
if lscore <= ascore or cnt < 0:
continue
lion[10] = cnt
lion[11] = lscore - ascore
if compare(lion, ans):
ans = lion[:]
if ans[-1] == -1:
return [-1]
else:
ans.pop()
return ans
- 그리디 + 재귀
위의 비트마스킹과 비슷한 방법으로 재귀를 이용해서 해결할수도 있다.
인덱스마다 라이언이 점수를 얻어갈때/얻어가지 못할때를 기준으로 가지치기를 통해 라이언의 점수를 얻고, 인덱스가 마지막인데 화살이 남았다면 0점에 모두 몰아주었다.
answer = [-1] * 12
def compare(a, b):
return a[::-1] > b[::-1]
def solution(n, info):
dfs(n, 0, [0] * 12, info)
answer.pop()
return answer
def dfs(arrow_left, idx, lion, apeche):
global answer
if arrow_left < 0:
return
if idx >= 10: ## dfs의 끝
lscore = 0
ascore = 0
lion[10] = arrow_left
print(arrow_left,lion)
for j in range(10):
if apeche[j] == 0 and lion[j] == 0:
continue
if lion[j] > apeche[j]:
lscore += (10 - j)
else:
ascore += (10 - j)
if lscore > ascore:
lion[11] = lscore - ascore
if compare(lion, answer):
answer = lion[:]
return
lion[idx] = apeche[idx] + 1
dfs(arrow_left - (apeche[idx] + 1), idx + 1, lion, apeche)
lion[idx] = 0
dfs(arrow_left,idx+1,lion,apeche)
꾸준히 공부하자