프로그래머스 - 카운트 다운 파이썬

문제

프로그래머스

문제 설명 이미지

 

문제 정리 

용어 정리

- 카운트 다운 = 무작위로 정해진 점수를 다트로 깎아서 0점을 만드는 게임 

- 점수 설명 

싱글 - 해당 수 만큼 점수 얻음(1,2,3....20까지의 점수)

더블 - 해당 수 두 배 만큼 점수 얻음(2,4,6...40까지의 점수)

트리플 - 해당 수 세 배 만큼 점수 얻음(3,6,9....60까지의 점수)

불, 아우터 불 - 50점 얻음 

 

경기 정리 

- 한줄 정리: 빨리 0점 만들기, 같으면 '싱글', '불' 최대한 많이 던지기 

- 한 게임에는 두 선수 참가 

- 교대로 한 번씩 던지는 방식 

- 가장 먼저 0점을 만든 선수가 승리 

- 두 선수가 같은 라운드에 0점이면, '싱글', '불'을 더 많이 던진 선수가 승리

- 이것도 같으면 선공이 승리 

 

제한사항 

- target은 1부터 10만의 범위

 

접근방법 

- 완탐으로 풀면 시간초과일 것 

- DP로 풀어야 하지 않을까 

 

코드 

def solution(target):
    # target까지 도달하는 데 필요한 최소 다트 수와 "싱글" 또는 "불"을 맞춘 횟수를 기록하는 배열
    # 최댓값으로 초기화
    dp = [[float('inf'), 0] for _ in range(300000)]

    # 가능한 과녁 값들
    targetList = [i + 1 for i in range(20)]

    # 시작 지점의 다트 수는 0으로 초기화
    dp[0][0] = 0

    # target까지 탐색
    for i in range(target):
        def updateDart(addIdx, count):
            # 던진 다트 수를 갱신할 필요가 있는 경우
            if dp[i + addIdx][0] >= dp[i][0] + 1:
                if dp[i + addIdx][0] == dp[i][0] + 1:
                    # 기존 값과 비교하여 "싱글" 또는 "불"을 맞춘 횟수(합) 갱신
                    dp[i + addIdx][1] = max(dp[i + addIdx][1], dp[i][1] + count)
                else:
                    # 던진 다트 수와 "싱글" 또는 "불"을 맞춘 횟수(합)을 갱신
                    dp[i + addIdx] = [dp[i][0] + 1, dp[i][1] + count]

        # 모든 과녁 값에 대해 확인
        for j in targetList:
            # 싱글, 더블, 트리플을 순서대로 적용하여 갱신
            for multiplier, hitCount in [[1, 1], [2, 0], [3, 0]]:
                updateDart(j * multiplier, hitCount)

        # "불"에 대해서도 확인하여 갱신
        updateDart(50, 1)

    # target까지 도달하는 데 필요한 최소 다트 수와 "싱글" 또는 "불"을 맞춘 횟수 반환
    return dp[target]

 

코드의 시간복잡도: O(n)

첫 번째 반복문은 target까지 반복하고, 두 번째 반복문은 targetList의 크기만큼 반복하며, 세 번째 반복문은 상수 시간에 실행 updateDart 함수도 상수 시간에 실행

따라서 전체 시간 복잡도는 O(target * |targetList|)

 

공간복잡도: O(300,000)

dp 배열의 크기는 300,000이며, 각 원소는 [float('inf'), 0] 형태의 리스트임 따라서 dp 배열의 공간 복잡도는 O(300,000)

• targetList 배열의 크기는 고정되어 있으며, 상수 크기이므로 공간 복잡도에는 영향을 미치지 않음
• updateDart 함수는 상수 공간을 사용하므로 공간 복잡도에는 영향을 미치지 않음