[백준 1757번] 파이썬 - 달려달려

백준 1757 - 달려달려

시간 제한 2초, 메모리 제한 128MB

# 조건

• 월드 학생들은 운동장을 도는데 정확히 N분에 완주할 수 있는 시간 안배능력까지 갖추게 되었다.
• 그래서 N분동안 학생들은 달릴지 아님 쉴지 결정하여야 한다.
• 그러나 학생들도 인간이기 때문에 계속 달릴 수는 없다.
• “지침 지수”라는 것이 있어서 1분을 달린다면 “지침 지수”는 1이 올라간다.
• 반대로 1분을 쉰다면 “지침 지수”는 1이 내려간다.
• 또한 이 “지침 지수”가 M보다 커지면 학생들은 더 이상 달릴 수가 없다.
• 아주 특이하게도 학생들은 시간에 따라 달릴 수 있는 거리가 다르다.
  • 만약 I분에 달렸다면 Di 만큼의 거리를 달릴 수 있다. (i분을 달렸다는 것이 아니라 I분이 되는 때에 달렸다는 뜻임)
• 또한 학생들이 쉬기 시작하면 지침지수가 0이 되기 전에는 다시 달릴 수가 없다.
• 물론 이 달리기가 끝나면 학생들은 다시 공부를 해야한다.
• 그렇기 때문에 달리기가 끝난다음 지침지수가 0이 되지 않는다면 맑은 정신으로 문제를 풀 수가 없기 때문에 달리기가 끝나면 지침지수는 0이 되어야 한다.
• 월드학생들이 최대한 멀리 갈 수 있는 거리를 구해보자.

입력

• 첫째 줄에 운동할 시간 N(1 ≤ N ≤ 10000)과 M(1 ≤ M ≤ 500)이 주어진다.
• 이어서 N개의 줄에 i분에 달릴수 있는 거리 Di(0 ≤ Di ≤ 10,000)가 차례차례 주어진다.

출력

• 첫째 줄에 최대로 멀리 갈 수 있는 거리를 출력하라.

# 접근 방법

• 이전의 경로들의 값을 활용하기 위해 dp를 이용하여 풀어주는데 주의할 점은 지침 지수를 고려해야 된다는 것이다.
• 또한, 지침 지수는 달리면 +1, 쉬면 -1이 되지만 한 번 쉬면 0이 될 때까지 못 달린다라는 점을 잘 고려해주어야 된다.
• 따라서, 총 2개의 점화식을 구하여 풀어주었다.
• 직전의 사람의 dp값에 현재 사람의 달리는 거리를 더해주는 경우 => 지침 지수 + 1
  • dp[i][j] = dp[i-1][j-1] + dist[i]
• 직전 사람이 쉬었다는 가정하에 0이 될 때까지 쉬어주기
  • 이 경우에는 dp[i][0]과, j번째 전의 사람의 0값, j번째 전의 사람의 지침 지수 j의 값을 비교해주었다.
  • dp[i][0] = max(dp[i][0], dp[i-j][j], dp[i-j][0])
• dp[i][0] 값을 구할 때, dp[i-1][0]을 고려하지 않아 틀렸습니다를 받게 되었고 아래 고수 분의 풀이를 참고하여 해결하였다.
• dp는 케이스를 잘게 부수고 고려해야 될 점을 잘 찾는 것이 정말 중요한 문제인 것을 또 깨닫고 간다..

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N, M = map(int, input().split())  
dist = [0] + [int(input()) for _ in range(N)]  
dp = [[0] * (M+1) for _ in range(N+1)]  

for i in range(1, N+1):  
    for j in range(1, M+1):  
        dp[i][j] = dp[i-1][j-1] + dist[i]  
    for j in range(1, M+1):  
        if i-j < 0:  
            break;  
        dp[i][0] = max(dp[i][0], dp[i-j][j], dp[i-j][0])  

print(dp[N][0])