문제 출처
https://school.programmers.co.kr/learn/courses/30/lessons/92342
문제를 스스로 해결하였는가? -> X
한 달전, 처음 알고리즘 공부를 시작했을 때 DFS와 백트래킹에 대한 배경이 전혀 없는 상태에서 접했던 문제다. 프로그래머스에서 다른 사람의 풀이를 통해 솔루션을 참고했지만, 처음엔 솔루션을 보고 이해하는 것조차 힘들었다. 백준의 단계별 문제풀이에서 비슷한 알고리즘의 문제를 공부하고 다시 이 문제를 풀어보니 생각보다 잘 풀렸다. 아마 오랫동안 고민해서 소스코드 전체가 외워져서 그런 것 같다.
필요한 배경 지식
- 백트래킹
- DFS
주의할 점
- 라이언은 반드시 해당 과녁에 어피치보다 많은 개수를 맞춰야 점수를 가져갈 수 있다.
- 해당 과녁에 라이언, 어피치 모두 화살을 맞추지 못했다면 아무도 점수를 가져가지 못한다.
- 라이언이 가장 큰 점수 차로 이길 수 있는 방법이 여러 가지 일 경우 가장 낮은 점수를 더 많이 맞힌 경우를 return 해야한다.
풀이 과정
가장 먼저 라이언의 점수와 어피치의 점수가 주어졌을 때, 라이언의 점수를 계산하는 함수를 작성한다.
def score(ryan):
s = 0
for i in range(10):
if apeach[i] == ryan[i] == 0: continue
if apeach[i] < ryan[i]:
s += 10-i
else:
s -= 10-i
return s
다음으로 라이언의 점수를 ryan=[0,...,n] 부터 시작해 배열의 왼쪽으로 값을 하나씩 옮겨가며 점수를 계산하는 dfs 함수를 작성한다. 주의할 점 3에 의해 반드시 ryan=[0,...,n]에서 시작해야한다.
def dfs(idx, left):
nonlocal maxi, answer
if left == 0:
s = score(ryan)
if s > maxi:
maxi = s
answer = ryan[:]
return
# 11개 점수판을 모두 탐색했음에도 분배되지 않은 화살이 있다면 종료
if left != 0 and idx==-1:
return
# 남아있는 과녁을 1개씩 줄여가며 dfs 수행
for i in range(left, -1, -1):
ryan[idx] = i
dfs(idx-1, left-i)
전체 코드
def solution(n, apeach):
ryan = [0] * 11
answer = [0] * 11
def score(ryan):
s = 0
for i in range(10):
if apeach[i] == ryan[i] == 0: continue
if apeach[i] < ryan[i]:
s += 10-i
else:
s -= 10-i
return s
def dfs(idx, left):
nonlocal maxi, answer
if left == 0:
s = score(ryan)
if s > maxi:
maxi = s
answer = ryan[:]
return
if left != 0 and idx==-1:
return
for i in range(left, -1, -1):
ryan[idx] = i
dfs(idx-1, left-i)
maxi = 0
dfs(10, n)
return answer if maxi != 0 else [-1]
'알고리즘 (Python) > 프로그래머스' 카테고리의 다른 글
[프로그래머스][Level3] 징검다리 건너기 (파이썬) (1) | 2022.08.22 |
---|---|
[프로그래머스][Level2] 구명보트 (파이썬) (0) | 2022.08.13 |
[프로그래머스][Level2] 조이스틱 (파이썬) (0) | 2022.08.13 |
[프로그래머스][Level2] 다리를 지나는 트럭 (파이썬) (0) | 2022.08.13 |
댓글