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

문제

• 다트 과녁에는 1 부터 20 까지의 수가 하나씩 있고 각 수마다 "싱글", "더블", "트리플" 칸이 있다.
• "싱글"을 맞히면 해당 수만큼 점수를 얻고 "더블"을 맞히면 해당 수의 두 배만큼 점수를 얻고 "트리플"을 맞히면 해당 수의 세 배만큼 점수를 얻습니다. 가운데에는 "불"을 맞추면 50점을 얻는다.
• 최소한의 다트로 target 점수를 만들어야 한다.
  • 다트의 수가 동일하다면 "싱글" 또는 "불"을 최대한 많이 던지는 방법을 선택해야 한다.
• 1 <= target <= 100,000

 

풀이

• 요새 BFS/DFS 를 많이 풀어서인지 DFS가 먼저 떠오르긴 했지만, 이런류의 문제는 DP가 효율적이다.
• 1) 싱글과 불을 포함한 single 리스트와 더불과 트리플 점수를 포함한 double 리스트를 만든다.
• 2) dp[n] : n점 만드는데 필요한 [최소 다트 개수, 최대 싱글/불 개수]
• 3) 1점부터 target 점수까지 최소 다트 개수와 최대 싱글/불 개수를 갱신한다.
  • ( i-k) + k = i 를 이용한다.
  • 3-1) i-k 점수에서 싱글/불로 k점을 추가하는 경우
  • 3-2) i-k 점수에서 더불/트리플로 k점을 추가하는 경우
  • single과 double 리스트는 모두 정렬되어 있으므로 i-k 가 0보다 작아지는 경우에 그 이후 값은 모두 0보다 작으므로 반복문 탈출 (for 시간효율)

 

def solution(target):
    single = sorted([i for i in range(1, 21)]+ [50])		# single + bull
    double = sorted([2*i for i in range(1, 21)] + [3*i for i in range(1, 21)]) # double + triple
    
    # dp[n] : n점 만드는데 필요한 [최소 다트 개수, 최대 싱글/불 개수]
    dp = [[int(1e9), 0]] * (target+1)
    dp[0] = [0, 0]
    
    for i in range(1, target+1) :     
        for k in single:
            if i-k < 0 : break
            if dp[i][0] > dp[i-k][0] + 1:		# 다트 최소개수 갱신
                dp[i] = [ dp[i-k][0] + 1, dp[i-k][1] + 1]
            elif dp[i][0] == dp[i-k][0] + 1 :	# 싱글/불 최대개수 갱신
                dp[i][1] = max(dp[i][1], dp[i-k][1] + 1)
        
        for k in double:
            if i-k < 0 : break
            if dp[i][0] > dp[i-k][0] + 1:		# 다트 최소개수 갱신
                dp[i] = [ dp[i-k][0] + 1, dp[i-k][1]]
            elif dp[i][0] == dp[i-k][0] + 1 :	# 싱글/불 최대개수 갱신
                dp[i][1] = max(dp[i][1], dp[i-k][1])
        
    return dp[target]

 

References

• 프로그래머스 Lv3 카운트 다운