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

Об этом предложении

문제 요약 목표 점수 target 을 정확히 만들기 위해 다트를 던진다. 최적의 방법은 다음 우선순위로 결정한다. 던지는 다트 수를 최소화한다. 다트 수가 같으면 싱글 또는 불을 맞힌 횟수를 최대화한다. [최소 다트 수, 최대 싱글 또는 불 횟수] 를 반환한다. 핵심 아이디어 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을 선택한다. 풀이 과정 한 번에 만들 수 있는 점수와 싱글 또는 불 횟수 증가량을 만든다. dp[0] = [0, 0] 으로 초기화한다. 1점부터 target 점까지 순서대로 확인한다. 가능한 마지막 다트를 하나씩 적용해 이전 점수의 결과를 갱신한다. 다트 수가 더 적거나, 다트 수가 같으면서 싱글 또는 불 횟수가 더 많을 때만 갱신한다. 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에 반영할 수 있다.

Детали предложения

Провайдер

velog

Источник

velog-rss

Балл

54.34

Уверенность

49%