프로그래머스 다트 협회에서는 매년마다 새로운 특수 룰으로 다트 대회를 개최합니다. 이번 대회의 룰은 "카운트 다운"으로 "제로원" 룰의 변형 룰입니다. "카운트 다운"은 게임이 시작되면 무작위로 점수가 정해지고, 다트를 던지면서 점수를 깎아서 정확히 0점으로 만드는 게임입니다. 단, 남은 점수보다 큰 점수로 득점하면 버스트가 되며 실격 합니다.
다음 그림은 다트 과녁입니다.
다트 과녁에는 1 부터 20 까지의 수가 하나씩 있고 각 수마다 "싱글", "더블", "트리플" 칸이 있습니다. "싱글"을 맞히면 해당 수만큼 점수를 얻고 "더블"을 맞히면 해당 수의 두 배만큼 점수를 얻고 "트리플"을 맞히면 해당 수의 세 배만큼 점수를 얻습니다. 가운데에는 "불"과 "아우터 불"이 있는데 "카운트 다운" 게임에서는 구분 없이 50점을 얻습니다.
대회는 토너먼트로 진행되며 한 게임에는 두 선수가 참가하게 됩니다. 게임은 두 선수가 교대로 한 번씩 던지는 라운드 방식으로 진행됩니다. 가장 먼저 0점을 만든 선수가 승리하는데 만약 두 선수가 같은 라운드에 0점을 만들면 두 선수 중 "싱글" 또는 "불"을 더 많이 던진 선수가 승리하며 그마저도 같다면 선공인 선수가 승리합니다.
다트 실력에 자신 있던 종호는 이 대회에 출전하기로 하였습니다. 최소한의 다트로 0점을 만드는 게 가장 중요하고, 그러한 방법이 여러가지가 있다면 "싱글" 또는 "불"을 최대한 많이 던지는 방법을 선택해야 합니다.
목표 점수 target이 매개변수로 주어졌을 때 최선의 경우 던질 다트 수와 그 때의 "싱글" 또는 "불"을 맞춘 횟수(합)를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
크게 DP를 이용한 풀이법과 경로탐색을 이용한 풀이법이 존재한다. 다만, 경로탐색 알고리즘은 queue 혹은 stack 자료구조의 입출력 특성상 시간이 더 많이 소요될 수 있음을 알린다 (본 풀이는 경로탐색 알고리즘을 통해 이루어졌고, 상대적으로 엄청 느린 속도를 보였다)
풀이 이후에 다른 분들의 풀이를 봤는데, 확실히 이렇게 queue의 입출력을 통해 구현하는 것 보다 DP를 통한 탐색이 더 빠른 점을 볼 수 있었다.
다트를 한 번 던질 때의 경우의 수는 다음과 같다.
* 1~20까지의 점수. 1, 2, 3..... 20(싱글)
* 1~20까지의 점수의 2배. 2, 4, 6 .... 40 (더블)
* 1~20까지의 점수의 3배, 3, 6, 9 ... 60 (트리플)
* 불 (50점)
이 중 우리는 총 던진 다트의 수, 그리고 포함된 싱글 혹은 불의 개수를 가지고 문제를 풀이하여야 한다. 즉 이를 고려해 경로탐색 알고리즘을 수행하면 되는 것. DP로의 풀이는 따로 적지는 않겠지만, 핵심은 동일하다고 볼 수 있다. 다만 어떤 자료구조에 넣고 계속 비교해가느냐, 아니면 배열을 탐색하며 DP를 실행하느냐의 차이가 되겠다.
풀이 코드
from collections import deque
MAX = float('inf')
def solution(target):
dp = [[MAX, -MAX] for _ in range(target+1)]
q = deque([(0, 0, 0)])
while q :
score, dart, single = q.popleft()
for i in range(1, 21) :
for j in range(1, 4) :
_score = i*j + score
if _score > target :
continue
_single = single + 1 if j == 1 else single
if dp[_score][0] > dart + 1 or dp[_score][0] == dart + 1 and dp[_score][1] < _single :
dp[_score] = [dart+1, _single]
q.append((_score, dart+1, _single))
if score + 50 > target :
continue
if dp[score + 50][0] > dart + 1 or dp[score+50][0] == dart + 1 and dp[score + 50][1] < single + 1 :
dp[score+50] = [dart + 1, single + 1]
q.append((score+50, dart+1, single+1))
return dp[-1]
