23.04.26 파이썬 코딩 퀴즈#235 카운트 다운 (프로그래머스 스쿨)

이번 문제는 카운트 다운 문제이다.

다트 게임을 진행하는 문제이며, 무작위로 정해진 목표 점수를 다트를 던지면서 점수를 깎아서 정확히 0으로 만드는 게임이다.

다트판에는 1~20까지 점수가 있고, 싱글(1배),더블(2배), 트리플(3배) 의 점수를 획득할 수 있는 공간과 50점을 한번에 획득 가능한 정 가운데 불 이 존재한다.

최소한의 다트를 던져서 목표 점수를 만드는게 목적이며, 만약 그러한 방법이 여러가지가 있다면 '싱글' 또는 '불'을 최대한 많이 던지는 방법을 선택해야 한다.

입출력 예 2번을 살펴보자.

58점을 맞추는 방법은 여러가지 이다.

먼저 문제의 정답인 불(50) + 8 싱글이 가능하고.

그 다음은 20 더블 + 18 싱글, 19더블 + 20 싱글, 18더블 + 11더블 .... 등의 다트를 두 번 쏘아 맞추는 방법이 있다.

하지만 무제에서는 만약 최소한의 다트를 던지는 방법이 여러가지라면 '불' 또는 '싱글'을 최대한 많이 던지는 방법을 선택한다고 되어 있으므로, 총 던진 다트수가 2개이며, 이 중 2발을 '불' 또는 '싱글'로 사용한 불(50+ 8싱글이 문제의 정답이 된다.

 

최소한의 다트를 사용하는 문제라면 20트리플만을 이용해 점수를 다 깎고 남은 점수에 따라 불 또는 더블, 싱글로 점수를 깎으면 되겠지만, 위 문제는 경우의 수를 확인하고, 만약 여러개라면 불 또는 싱글을 가장 많이 이용한 방법을 택해야 한다.

먼저 싱글과 불, 더블과 트리플 점수로만 구성된 배열을 만들어 주었다.

그리고 dp 에는 해당 점수를 만들기 위한 최적의 다트 수를 넣어 주었다.

else 부분이 처음에 좀 어려웠는데, 40 이하는 싱글을 두번 사용해서 만드는게 최선이고, 50 이하는 싱글 한번, 더블 또는 트리플을 사용해서 만들 수 있었따. 그리고 만약 50을 초과하는 경우라면 싱글+불을 이용해서 만드는게 최선이다.

빠르게 탐색을 우해 max_dart 값을 설정해 주었다. 이때 50점 만 맞추는 경우와, 60점만 맞추는 경우를 계산하여 최대값을 이용한다.

그리고 [target, 0, 0] 을 q 에 넣어주고 while문을 돌게 된다.

여기서 한가지 중요한 사실은 어느 시점에 60점을 맞추고, 어느 시점에 50점을 맞추는게 유리한지 판단하는 것이다.

300을 예로 들면 50점 기준으로 [6,6] 이고 60점 기준으로 [5,0] 이다.

문제의 첫번째 조건이 최소한의 다트를 사용하는게 우선이므로 [5,0] 이 정답이다.

299를 살펴보면

1. 50+50+50+50+50[5,5] +49이고 49 는 트리플, 더블이 아니므로 [2,1] 이 된다. 따라서 [7,6] 이다. 50 만 사용

2. 50+60+60+60+60 [5,1] + 9 이고 9는 싱글[1,1] 이므로 최종적으로 [6,2] 이 된다. 50 1번 사용

3. 50+50+60+60+60 [5,2] + 19 이고 19는 싱글[1,1] 이므로 최종적으로 [6,3] 이 된다. 50 2번 사용

4. 50+50+50+50+60 [5,4] + 39 이고 39 는 트리플[1,0] 이므로 최종적으로 [6,4]가 된다. 50 4번 사용

...

위와 같이 300 미만의 경우에는 모든 경우의 수를 따져서 확인이 가능하다.

따라서 전달받은 target 이 300 이상 이라면 그 값을 300 미만으로 만들고 그 때 사용한 몫에서 4를 뺀 값을 이용하여 다시 q에 넣어주는 방법을 택하였다.

그리고 300미만의 값들에 대해서는 확실치 않기 때문에 50과 60을 뺀 두 개의 경우를 각 각 q에 넣어 주었다.

문제 자체가 어렵다기 보다는 이해력이 많이 요구되는 문제였다.