예시 5: 최대 배달 점수

📖 학습 내용

문제 설명

총 N개의 배달 역이 있고 각 역에서 M개의 이동 경로 중 하나를 선택할 수 있을 때, 0번 역에서 시작하여 배달을 완료하며 얻을 수 있는 최대 점수를 구합니다.

입력 형식

첫 줄 N, M / 둘째 줄 이동량 a0..aM-1 / 셋째 줄 각 역 점수 c0..cN-1 이 공백으로 주어집니다.

출력 형식

배달을 완료할 때 얻을 수 있는 최대 점수 1개를 출력합니다.

원문 예시

PDF 공식 예시 입력 6 2 / 2 3 / 1 0 30 100 30 30 의 출력은 131입니다.

📥 테스트 입력값

6 2
2 3
1 0 30 100 30 30

🔎 실행 결과

💡 힌트 코치

현재 역에서 갈 수 있는 다음 역들 중 최댓값을 뒤에서부터 DP로 채우면 효율적으로 풀 수 있습니다.

✅ 정답 공개

n, m = map(int, input().split())
steps = [int(x) for x in input().split()]
scores = [int(x) for x in input().split()]
dp = [0] * n
for i in range(n - 1, -1, -1):
    best_next = 0
    for step in steps:
        nxt = i + step
        if nxt < n and dp[nxt] > best_next:
            best_next = dp[nxt]
    dp[i] = scores[i] + best_next
print(dp[0])