카운트 다운
링크
[ 문제에 대한 이해 ]
- 다트 과녁에는 1부터 20까지의 수가 있고, 각 수마다 싱글, 더블, 트리플 칸이 있다.
- 최소한의 횟수로 점수를 0점으로 만드는 것이 1순위이다.
- 만약 최소한의 횟수로 만드는 방법이 여러가지가 있다면, 싱글 또는 불을 최대한 많이 던지는 방법을 사용해야 한다.
접근 방법
제한 사항을 확인한다.
- target은 1부터 10만의 범위를 가지기 때문에, 최대한 적은 시도 횟수로 탐색을 시도해야 한다.
탐색 횟수가 적은 방법으로 접근할 수 있는 방법은 그리디와 다이나믹 프로그래밍이 있다.
동전 문제를 생각해보자.
- 8이라는 금액을 1, 4, 5라는 동전으로 거슬러줄 수 있다고 생각하자. 5원을 내면 3원을 내기 위해 총 4개의 동전이 필요하지만, 4원을 낸다면 두 개의 동전만으로 8원을 만들 수 있다.
이 문제 또한 어떤 점수를 만들기 위해 필요한 다트 점수가 매우 다양하므로, 그리디로는 접근이 불가능하다.
또한 동전 문제와 동일하게 어떤 금액 i를 만들기 위해 4원의 동전을 내야 한다고 가정한다면, 3원을 만들기 위한 동전의 개수 + 1을 더한 값과 기존의 값 중 최솟값을 비교하여 반영하면 되고, 주어진 조건이 변하지 않으면 해당 금액에 대해서 늘 동일한 결과를 갖기 때문에 해당 값을 최종 해를 구하는 데 재사용할 수 있다.
따라서 다이나믹 프로그래밍으로 해결이 가능하다.
- 동전을 점수로 치환하면 동일한 원리로 해결이 가능함을 확인할 수 있다.
다만 이 경우는 한 뎁스 더 생각해야 할 필요가 있다.
최소의 다트 횟수로 점수를 완성하되, 같은 횟수라면 불 또는 싱글 횟수가 최대인 경우를 생각해줘야 한다.
따라서 싱글과 불로 만들수 있는 점수와, 싱글과 불로 만들 수 없는 점수를 나눈 테이블을 만들어 주었다.
# arr[0]은 싱글, 불로 만들 수 있는 점수
# arr[1]은 싱글, 불로 만들 수 없는 점수
def create_table():
arr = []
arr.append([i for i in range(1, 21)])
arr[0].append(50)
nxt = []
for i in range(1, 21):
for j in range(2, 4):
ret = i * j
if ret > 20:
nxt.append(ret)
arr.append(list(set(nxt)))
return arr시도 횟수와 최대 싱글 + 불 횟수 합을 저장해야 하므로, 2차원 배열로 dp배열을 선언한다.
모든 점수를 순회하면서 개수를 세되, 현재 최솟값과 동일한 시도 횟수라면, 최대 싱글 + 불 횟수를 저장할 수 있도록 한다.
정답 코드
INF = 987654321
def create_table():
arr = []
arr.append([i for i in range(1, 21)])
arr[0].append(50)
nxt = []
for i in range(1, 21):
for j in range(2, 4):
ret = i * j
if ret > 20:
nxt.append(ret)
arr.append(list(set(nxt)))
return arr
def solution(target):
table = create_table()
dp = [[INF, 0] for _ in range(target + 1)]
dp[0][0] = 0
for i in range(1, target + 1):
for j in range(2):
for k in range(len(table[j])):
prev = i - table[j][k]
if prev < 0:
continue
total, valid = dp[prev][0] + 1, dp[prev][1] + 1 - j
if total < dp[i][0]:
dp[i] = [total, valid]
elif total == dp[i][0]:
dp[i] = [total, max(dp[i][1], valid)]
return dp[target]
