JS Coding Blog

거리 감쇠가 있는 최고 체크포인트 점수

자바스크립트 코딩테스트 문제로 monotonic-queue-dp 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today medium monotonic-queue-dp 함수명: maxDecayedCheckpointScore 제한 시간: 300ms

체크포인트를 건너뛰며 이동할 때, 이동 거리만큼 점수가 깎이는 조건에서 마지막 체크포인트까지 얻을 수 있는 최고 점수를 구하세요.

문제 설명

정수 배열 scores와 한 번에 이동할 수 있는 최대 거리 maxJump가 주어집니다.

처음에는 0번 체크포인트에 있으며, 시작하자마자 scores[0]점을 얻습니다. 이후 현재 위치 j에서 더 큰 인덱스 i로 이동할 수 있는데, 이때 1 <= i - j <= maxJump여야 합니다.

i번 체크포인트에 도착하면 scores[i]점을 얻고, 이동 거리 i - j만큼 점수가 깎입니다.

마지막 체크포인트인 scores.length - 1번에 반드시 도착해야 합니다. 가능한 경로 중 최종 점수의 최댓값을 반환하는 maxDecayedCheckpointScore 함수를 작성하세요.

제한사항

  • 1 <= scores.length <= 100,000
  • 1 <= maxJump <= scores.length
  • -1,000,000 <= scores[i] <= 1,000,000
  • 한 번 이동할 때는 반드시 오른쪽으로 이동합니다.
  • 시작 체크포인트의 점수는 감쇠 없이 그대로 얻습니다.
  • 마지막 체크포인트까지 항상 도착할 수 있습니다.
  • 반환값은 가능한 최종 점수의 최댓값입니다.

예시

  • 입력: scores = [5, -2, 4, 3], maxJump = 2 → 출력: 9
  • 입력: scores = [10, -5, -5, 20], maxJump = 1 → 출력: 17
  • 입력: scores = [0, 100, -100, 100], maxJump = 3 → 출력: 197
  • 입력: scores = [-3, -2, -1], maxJump = 2 → 출력: -6

힌트

  • dp[i]를 i번 체크포인트에 도착했을 때의 최고 점수라고 생각해 보세요.
  • j에서 i로 이동하면 후보 점수는 dp[j] + scores[i] - (i - j)입니다.
  • 식을 scores[i] - i + (dp[j] + j)로 바꾸면, 최근 maxJump개 후보 중 dp[j] + j가 가장 큰 값만 빠르게 찾으면 됩니다.

해설

가장 직접적인 DP는 다음과 같습니다.

dp[i] = max(dp[j] + scores[i] - (i - j))

여기서 j는 i - maxJump <= j < i를 만족하는 이전 체크포인트입니다.

이 식을 정리하면 다음처럼 바뀝니다.

dp[i] = scores[i] - i + max(dp[j] + j)

즉, 매 위치 i마다 최근 maxJump개 이전 위치 중 dp[j] + j가 가장 큰 후보만 알면 됩니다. 이를 매번 선형 탐색하면 최악의 경우 O(n * maxJump)가 되므로 입력이 클 때 느립니다.

대신 단조 큐를 사용합니다.

  1. 큐에는 후보 인덱스 j를 저장합니다.
  2. 큐의 맨 앞 후보가 i - maxJump보다 작으면 이동 가능 범위를 벗어났으므로 제거합니다.
  3. 큐의 맨 앞은 항상 dp[j] + j가 가장 큰 후보가 되도록 유지합니다.
  4. dp[i]를 계산한 뒤, 새 후보 i를 큐에 넣습니다.
  5. 새 후보보다 dp[j] + j 값이 작거나 같은 뒤쪽 후보들은 앞으로 최댓값이 될 수 없으므로 제거합니다.

예를 들어 scores = [5, -2, 4, 3], maxJump = 2라면 0 -> 2 -> 3으로 이동하는 것이 좋습니다.

  • 시작 점수: 5
  • 0 -> 2: scores[2] - 2 = 4 - 2, 누적 7
  • 2 -> 3: scores[3] - 1 = 3 - 1, 누적 9

따라서 정답은 9입니다.

각 인덱스는 큐에 한 번 들어가고 한 번만 나오므로 시간 복잡도는 O(n)입니다. dp 배열을 저장하면 공간 복잡도는 O(n)이고, 큐에 후보 점수까지 함께 저장하면 O(maxJump)로 줄일 수 있습니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.