[Python/파이썬] 백준 1757번 달려달려

1757번: 달려달려

 

코드

n, m = map(int, input().split())
d = [0]+[int(input()) for _ in range(n)]

dp = [[0]*(m+1) for _ in range(n+1)]  # i분에 지침 지수가 j일 때 최대 이동 거리
for i in range(1, n+1):
    dp[i][0] = max(dp[i-1][0], dp[i][0])    # 지침 지수 0에서 계속 쉬는 경우
    for j in range(1, m+1):
        if j == 1 or dp[i-1][j-1] != 0:  # 달리기
            dp[i][j] = dp[i-1][j-1]+d[i]
            if (i+j <= n):  # i분이고 지침 지수 j인 상황에서 쭉 쉬는 경우
                dp[i+j][0] = max(dp[i][j], dp[i+j][0])

print(dp[n][0])

 

dp[n][m] : n분에 지침 지수가 m일 때의 최대 이동 거리

 

n분에 지침 지수가 0인 경우는 n분 이전에 지침 지수가 0일 때부터 n분까지 계속 쉬거나 어느 순간부터 쉬기 시작하여 n분에 지침 지수 0을 찍는 2가지 경우가 있다. 

예를 들어, 아래의 예시에서 4분에 지침 지수가 0이 되는 경우는 ①3분부터 0인 상태로 유지되거나 ②3분이고 지침 지수가 1일 때와 2분이고 지침 지수가 2일 때에서부터 내려오는 방법이 있다.

 

그리고 지침 지수가 1 이상인 경우에는 n분에 지침 지수가 m일 때의 최대 거리인 dp[n][m]이 1분 전 지침 지수가 1 작았던 거리(dp[n-1][m-1])에서 n분째에 달릴 수 있는 거리(d[i])를 더해주면 되는데, j가 1이거나 dp[n-1][m-1] ≠ 0인 경우에만 n분에 지침 지수 m까지 도달할 수 있다.

 

dp[n][m] 값을 채워준 뒤에는 지금 상황(n분에 지침 지수가 m)에서 지침 지수가 0이 될 때까지 쉬는 경우를 계산하기 위해 i+j ≤ n인 경우 dp[i+j][0]의 값을 max(dp[i][j], dp[i+j][0])으로 갱신해준다.