[프로그래머스] 카운트 다운

문제 요약

목표 점수 target을 정확히 만들기 위해 다트를 던진다.

최적의 방법은 다음 우선순위로 결정한다.

1. 던지는 다트 수를 최소화한다.
2. 다트 수가 같으면 싱글 또는 불을 맞힌 횟수를 최대화한다.

[최소 다트 수, 최대 싱글 또는 불 횟수]를 반환한다.

핵심 아이디어

dp[score]를 정확히 score점을 만드는 최적의 결과라고 정의한다.

dp[score] = [최소 다트 수, 그때의 최대 싱글 또는 불 횟수]

마지막 다트로 얻은 점수가 points라면, 그 직전에는 score - points점을 만들었어야 한다.

dp[score] = dp[score - points] + 마지막 다트 정보

각 점수에서 가능한 모든 마지막 다트를 비교하면 된다.

다트 점수와 싱글 횟수

한 번의 다트로 만들 수 있는 점수는 다음과 같다.

• 싱글: 1 ~ 20점, 싱글 또는 불 횟수 1 증가
• 더블: 2 ~ 40점, 횟수 증가 없음
• 트리플: 3 ~ 60점, 횟수 증가 없음
• 불: 50점, 싱글 또는 불 횟수 1 증가

같은 점수를 만들 수 있는 방법이 여러 개여도 모두 비교 기준에 따라 처리한다. 예를 들어 6점은 싱글 6, 더블 3, 트리플 2로 만들 수 있고, 다트 수가 같으므로 싱글 6을 선택한다.

풀이 과정

1. 한 번에 만들 수 있는 점수와 싱글 또는 불 횟수 증가량을 만든다.
2. dp[0] = [0, 0]으로 초기화한다.
3. 1점부터 target점까지 순서대로 확인한다.
4. 가능한 마지막 다트를 하나씩 적용해 이전 점수의 결과를 갱신한다.
5. 다트 수가 더 적거나, 다트 수가 같으면서 싱글 또는 불 횟수가 더 많을 때만 갱신한다.

Python 코드

def solution(target):
    throws = [(50, 1)]

    for number in range(1, 21):
        throws.append((number, 1))       # 싱글
        throws.append((number * 2, 0))   # 더블
        throws.append((number * 3, 0))   # 트리플

    infinity = target + 1
    dp = [(infinity, -1) for _ in range(target + 1)]
    dp[0] = (0, 0)

    for score in range(1, target + 1):
        for points, single_or_bull in throws:
            if score < points:
                continue

            previous_darts, previous_singles = dp[score - points]

            if previous_darts == infinity:
                continue

            candidate_darts = previous_darts + 1
            candidate_singles = previous_singles + single_or_bull
            current_darts, current_singles = dp[score]

            if (
                candidate_darts < current_darts
                or (
                    candidate_darts == current_darts
                    and candidate_singles > current_singles
                )
            ):
                dp[score] = (candidate_darts, candidate_singles)

    return list(dp[target])

예시

target = 21

7 트리플로 한 번에 21점을 만들 수 있다.

다트 수: 1
싱글 또는 불 횟수: 0
결과: [1, 0]

target = 58

불 50점과 싱글 8점을 사용하면 2번의 다트로 58점을 만든다.

불 50 + 싱글 8 = 58
다트 수: 2
싱글 또는 불 횟수: 2
결과: [2, 2]

시간 복잡도

한 번의 다트로 만들 수 있는 경우는 불을 포함해 61개다.

T를 목표 점수라고 하자.

• 시간 복잡도: O(T * 61) = O(T)
• 공간 복잡도: O(T)

target <= 100,000이므로 충분히 빠르게 동작한다.

정리

각 점수마다 최소 다트 수와 최대 싱글 또는 불 횟수를 함께 저장한다. 다트 수를 우선 비교하고, 동점일 때만 싱글 또는 불 횟수를 비교하면 문제의 우선순위를 그대로 DP에 반영할 수 있다.