백준 1757 달려달려 Python

🐸 문제 정보

1757번: 달려달려

 

🤖 알고리즘

DP

 

⏱️ 풀이 시간

60+m

 

📝 풀이

이틀동안 풀지 못했다...

처음에 시도했던 방법은 3차원 DP였는데, 해당 분에 뛴 경우와 쉰 경우를 분리해서 마지막에 지침지수가 0인 경우 최대값을 구했다.

하지만 이렇게 풀면 어떻게해도 메모리 초과가 난다...

 

정말 많이 틀렸다..

 

올바른 풀이 방법은 아래와 같다.

1. DP로 풀되, 2차원이면 충분하다.
2. 우선 지침지수가 0인 경우, 즉 dp[i][0]에는 직전에 쉬고 현재 분에도 쉰 거리를 대입한다.
   • dp[i][0] = dp[i - 1][0]
3. 지침지수가 1보다 큰 경우, 즉 dp[i][j]에는 직전까지 달린 거리 + 현재 분떄 달릴 수 있는 거리를 대입한다.
   • dp[i][j] = dp[i - 1][j - 1] + d[i]
4. 이 때, 지침지수가 0인 경우(dp[i][0])를 두 개의 값 중 최대값으로 결정한다.
   • 2단계에서 지정해준 직전에도 쉬고 현재 분에도 쉰 거리
     • dp[i][0]
   • 현재까지 특정 지침 지수만큼 쉰 거리
     • dp[i - j][j] → [현재 시간 - 지침지수][지침지수]

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
d = [0] + list(int(input().rstrip()) for _ in range(n))
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    dp[i][0] = dp[i - 1][0]
    for j in range(1, m + 1):
        dp[i][j] = dp[i - 1][j - 1] + d[i]
        dp[i][0] = max(dp[i][0], dp[i - j][j]) # 쭉 쉬는 경우 dp[현재 분 - 지침지수][지침지수] 하면 현재 분까지 오는 동안 지침지수가 0이된다.
print(dp[-1][0])