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

문제

카운트 다운

https://school.programmers.co.kr/learn/courses/30/lessons/131129

 

 

풀이

설명

목표 점수가 주어졌을 때, 최선의 경우 던질 다트 수와 그때의 싱글 또는 불을 맞춘 횟수를 구하는 문제입니다.

 

DP로 해결할 수 있습니다.

 

최선의 경우란, 던질 다트 수를 최소화하고, 다트 수가 같을 경우, 싱글 또는 불을 맞춘 횟수를 최대화한 경우를 말합니다.

 

다트 하나를 던져서 획득할 수 있는 스코어는 다음과 같습니다.

• 1 ~ 20
• (1 ~ 20) * 2
• (1 ~ 20) * 3
• 50

 

dp[i]는 i점을 만들기 위해 필요한 [다트 수, 싱글 또는 불을 맞춘 횟수]입니다.

i점은 (i - 스코어)점에 다트 한 개를 추가로 던져 구할 수 있습니다.

가능한 스코어를 전부 시도해 보면서 가장 최선의 경우를 구하면 됩니다.

 

새 다트 수는 기존 다트 수에 1을 더한 값이고, 새 싱글 또는 불을 맞춘 횟수는 기존 값에 해당 스코어가 싱글 또는 불일 경우 1을 더해준 값입니다.

새 다트 수가 기존 다트 수보다 작을 경우, 다트 수, 싱글 또는 불을 맞춘 횟수 모두 업데이트해줍니다.

새 다트 수와 기존 다트 수가 동일할 경우, 후자만 최댓값으로 업데이트해줍니다.

 

예시 코드

function solution(target) {
  const scores = [];

  for (let i = 1; i <= 20; i++) {
    scores.push(i);
    scores.push(i * 2);
    scores.push(i * 3);
  }
  scores.push(50);

  const dp = Array.from({ length: target + 1 }, () => [Infinity, 0]);
  dp[0] = [0, 0];

  for (let i = 1; i <= target; i++) {
    for (const score of scores) {
      if (i < score) continue;
      const [darts, singles] = dp[i - score];
      const newDarts = darts + 1;
      const newSingleOrBulls = singles + (score === 50 || score <= 20 ? 1 : 0);

      if (newDarts < dp[i][0]) dp[i] = [newDarts, newSingleOrBulls];
      else if (newDarts === dp[i][0])
        dp[i][1] = Math.max(dp[i][1], newSingleOrBulls);
    }
  }

  return dp[target];
}