프로그래머스 LEVEL 3(카운트 다운)

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2022-12-21

  • 해결 방법 :

    • dp를 통해 문제 해결
      • 입력받은 target + 60의 길이만큼 dp 초기화
        • 가장 높은 점수인 20의 트리플만큼 저장해야 하기 때문에 60만큼 더함
        • 이 때 dp의 초기값은 [Infinity, 0]로 각각 던진 다트 수, 싱글 또는 불을 맞춘 횟수의 합을 의미
      • dp의 처음인 dp[0][0] 0으로 초기화
      • 0부터 target까지 돌고,
        • targetList(1 ~ 20)를 돌며
          • 각각 [[1, 1], [2, 0], [3, 0]]에 대한 check() 수행 (불을 제외한 부분을 맞출 경우)
          • 이 때 싱글인 경우는 count을 1로, 나머지는 0으로 설정
        • 불을 맞춘 경우까지 check()
      • check()함수 속 dp의 업데이트 조건은
        • dp의 다음 인덱스 값의 던진 다트 수가 현재 한번 더 던졌을 경우와 동일한 경우
          • 싱글 또는 불을 맞춘 횟수의 합이 더 많은 값으로 업데이트
        • dp의 다음 인덱스 값의 던진 다트 수가 현재 한번 더 던졌을 때 보다 많은 경우
          • 현재 한번 더 던진 경우의 값으로 업데이트

  • 회고 :

    • x

  • 코드

    function solution(target) {
  const dp = Array.from({ length: target + 60 }, () => [Infinity, 0]);
  const targetList = Array.from({ length: 20 }, (_, i) => i + 1);
  dp[0][0] = 0;

  const check = (i, j, count) => {
    const next = i + j;

    if (dp[next][0] === dp[i][0] + 1) {
      dp[next][1] = Math.max(dp[next][1], dp[i][1] + count);
    } else if (dp[next][0] > dp[i][0] + 1) {
      dp[next] = [dp[i][0] + 1, dp[i][1] + count];
    }
  };

  for (let i = 0; i < target; i++) {
    for (const t of targetList) {
      [
        [1, 1],
        [2, 0],
        [3, 0],
      ].forEach(([value, count]) => {
        check(i, t * value, count);
      });
    }

    check(i, 50, 1);
  }

  return dp[target];
}

  • 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges