[Programmers] 카운트 다운

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/131129#

프로그래머스

 

target이 최대 10만 점이고 다트는 한 턴당 최대 60점을 얻을 수 있기 때문에 단순 구현으로 접근하면 TLE가 발생합니다.

따라서 DP로 풀어야하는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. cache 벡터를 0 인덱스이므로 크기는 target + 1만큼 그리고 모든 인덱스를 {0, 0}으로 초기화해줍니다.

2. 모든 경우의 수를 확인하기 위해 모든 케이스에 대해 다트를 던져보고 가능한 케이스일 경우 cache를 업데이트해 줍니다.

2.1 여기서 불가능한 케이스의 여부는 크게 세 가지로 판단하며 아래 조건에 해당하지 않을 경우 가능하다고 판단합니다.

2.1.1 다트를 던졌을 때 점수가 0 미만이 될 경우 불가능한 케이스로 판단합니다.

2.1.2 다트를 던졌는데도 불구하고 던지기 전 cache에 저장된 던진 횟수와 같거나 적다면 모순이므로 불가능한 케이스로 판단합니다.

2.1.3 다트를 던진 횟수가 딱 한 번 차이 나고 "싱글" 또는 "불"을 맞춘 횟수를 업데이트하기 전인 상태인데 이미 "싱글" 또는 "불"을 맞춘 횟수가 업데이트 전 cache보다 높을 경우 모순이므로 불가능한 케이스로 판단합니다.

2.2 2.1.1 ~ 2.1.3 조건들에 해당하지 않을 경우 가능한 케이스로 판단해 cache를 업데이트합니다.

3. 2번 과정을 통해 도출해 낸 최종 결과를 반환해 줍니다.

 

 

개발환경: Programmers IDE

지적, 조언, 질문 환영합니다! 질문 남겨주세요~