99클럽 코테 스터디 20일차 TIL - [프로그래머스/파이썬] - 카운트 다운

프로그래머스 - 카운트 다운

프로그래머스

 

• 카운트 다운 : 주어진 숫자를 다트를 던져 해당 스코어에 도달하는 게임
• 싱글 : 다트가 해당 칸에 꽂히면 해당 하는 점수를 획득
• 더블 : 싱글  * 2
• 트리플 : 싱글 * 3
• 불 : 정 가운데 맞히면 50점. 외곽은 25, 안쪽은 50이나 본 게임에서는 50으로 통일

※ 2가 주어졌으면 한 개의 다트로 싱글 2나 더블 1, 혹은 싱글 1을 두 개의 다트를 이용하여 맞춰 2를 달성. 초과달성 시 실격

 

1. 최소한의 다트로 0점 만들기.
2. 1번의 경우의 수가 여러개라면, 싱글 + 불 이 가장 많은 던지는 방법을 선택
3. answer = [던진 다트 수, 싱글 + 불에 던진 다트 수]

예로, target = 20이라면 1번을 만족하는 경우의 수는 20 싱글, 10 더블 이 있을 것이다. 

answer = [1, 1], [1, 0] 이 되며, 이때 선택해야할 경우의 수는 [1,1] 이다.

 

제한사항

• 1 <= target <= 100,000

풀이

def solution(target):
    # 점수 업데이트를 위한 내부 함수 정의
    # score: 더할 점수, single: 싱글 점수 여부 (싱글일 때만 두 번째 요소 증가)
    def update_dp(score, single=True):
        # target 점수까지 반복
        for n in range(target + 1):
            next_score = n + score  # 다음 점수 계산
            if next_score > target:  # 목표 점수를 초과하는 경우 루프 중단
                break
            # dp 배열 업데이트 조건 확인 및 업데이트
            if dp[next_score][0] > dp[n][0] + 1 or \
                    (dp[next_score][0] == dp[n][0] + 1 and dp[next_score][1] < dp[n][1] + single):
                dp[next_score] = [dp[n][0] + 1, dp[n][1] + single]

    # dp 배열 초기화 (무한대로 설정하여 최소값 찾기 용이하게 함)
    dp = [[float('inf'), -1] for _ in range(target + 1)]
    dp[0] = [0, 0]  # 0점일 때의 기본값 설정

    # 1점부터 20점까지 반복하여 싱글, 더블, 트리플 점수 업데이트
    for i in range(1, 21):
        update_dp(i)  # 싱글
        update_dp(i * 2, False)  # 더블 (싱글이 아니므로 두 번째 요소 증가 안 함)
        update_dp(i * 3, False)  # 트리플 (싱글이 아니므로 두 번째 요소 증가 안 함)

    update_dp(50)  # 불 (50점)

    return dp[target]  # 목표 점수에 해당하는 dp 배열의 값을 반환

1. dp 테이블을 만들어 [최소값, 최대값] 이 입력되어야 하기 때문에 [최대값(inf), 최소값(0)]으로 시작한다.
2. 맞힐 수 있는 다트 점수 판을 list로 만들고 시작 지점을 0,0 으로 초기화 한다.
3. target만큼 돌면서 dart함수를 만들어 던진 다트 수를 갱신할 필요가 있는 경우와 싱글 또는 불 을 맞춘 경우를 갱신한다.
4. 이를 싱글, 더블, 트리플 순서대로 적용하여 갱신. 싱글은 1,1, 더블은 2,0, 트리플은 3,0 으로 하여 정해진 배수만큼 곱해주고, 싱글은 뒤의 인덱스도 1을 더해준다
5. 마지막으로 불에 대해서도 추가를 해주면 dp[target]에 있는 값을 return 한다.