문제
https://school.programmers.co.kr/learn/courses/30/lessons/131129
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 요약
위와 같은 과녁판이 주어지고 맞추어야할 점수 target이 주어질 때, 해당 점수를 얻기 위해 던져야하는 최소한의 다트 개수를 구하는 문제입니다. 이 때, 다트의 종류는 더블, 트리블, 불, 싱글 4종류가 나올 수 있는데 "불" 또는 "싱글"을 더 많이 던진 선수가 승리하는 구조로 "불" 또는 "싱글"을 최대한으로 던져야 합니다.
던질 최소한의 다트 수와 그 때의 "싱글" 또는 "불"을 맞춘 횟수를 순서대로 배열에 담아 반환하는 문제입니다.
풀이
경우의 수를 구하는 문제입니다. 하지만 경우의 수를 구한다고 매 경우때마다 던질 수 있는 다트의 모든 경우의 수를 구한 후에 최선의 케이스를 고르면 안됩니다. target이 100,000(10만)인 경우의 최선의 다트 수를 구할 경우 나올 수 있는 경우의 수는 너무 많습니다. (일반적으로 중복되지 않는 피보나치 수열을 생각할 수 있습니다.)
그럼 매 경우마다 최선의 다트 수를 바로 구할 수 있어야합니다. 그러기 위해서 필요한 알고리즘은 다이나믹 프로그래밍입니다. dp[i]를 점수 i점을 던지기 위한 최선의 케이스(배열 - [던진 최소한의 다트 수, "싱글" 또는 "불"을 맞춘 횟수])라고 합니다. 그리고 초기값을 생각해보면 아래와 같습니다. i가 70까지의 초기값을 생각할 수 있습니다.
(1) i가 1 ~ 20, 50일 때 - [1,1]
(2) i가 21 ~ 60 사이의 3의 배수일 때 - [1,0]
(3) i가 21 ~ 40 사이의 2의 배수일 때 - [1,0]
(4) i가 40이하의 나머지 수 - [2,2] (싱글 2번)
(5) i가 50 ~ 70 사이의 수일 때 - [2,2] (불 + 싱글)
(6) i가 70이하의 나머지 수 - [2,1] ((2), (3)케이스 + 싱글)
70 이후부터는 "불" 50점 또는 "트리플" 60점을 맞춰서 점수를 획득하는 것이 최소한의 다트 수를 던져 획득하는 방법입니다. 두 가지 케이스 모두를 고려해야 하는 이유는 던진 다트 수가 같을 경우 "불" 또는 "싱글"을 더 많이 던진 선수가 승리하기 때문입니다.
만약 80점을 던져야할 때는 dp[30] + "불" = [2,1] 과 dp[20] + "트리플" = [2,1] 두 경우를 문제의 조건대로 비교해서 최선의 방법으로 dp[80]을 업데이트합니다.
풀이 코드
'Algorithm' 카테고리의 다른 글
| [leetcode] Longest Substring Without Repeating Characters (swift) (0) | 2022.12.18 |
|---|---|
| [leetcode] Add Two Numbers (swift) (0) | 2022.12.18 |
| [Programmers] 파괴되지 않은 건물 - swift (Level 3) (0) | 2022.11.02 |
| [Programmers] 표 편집 - swift (Level 3) (0) | 2022.11.01 |
| [Programmers] 등산 코스 정하기 - swift (Level 3) (0) | 2022.10.30 |