백준 1757(달려달려) - 해결

달려달려

 

문제

어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정확히 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 문제인데 역시 짜는 건 헷갈렸다.

그러다 생각해낸 것이 N * (M+1) 짜리 dp 를 만들어서 하는 것.

요즘 보통 dp 문제를 이렇게 푸는 것 같다.

문제가 시간을 따라 하는 것이고 행동에 따라 변하는 변수가 변하고 제한이 있는 문제를 할 때,

시간을 따라 움직이는 방식으로 하고 행동에 따라 M 을 변화시킨다.

해당 문제에서 처음에는 가거나 안 가거나로 초기 세팅을 하고 

한 칸 씩 앞으로 가면서 크게 지침 지수가 0 일 때, M 일 때, 그리고 나머지 일 때로 나눠서 구분하고 

각 칸에서 쉴 때 랑 앞으로 갈 때를 구분해서 수행하고 지침 지수가 M 일 때는 쉬는 방법만 사용.

그리고 중요한 것이 쉴 때는 한번에 다 쉴 때 칸으로 이동하고

이동할 때도 행 + 열이 N 이상이면 거기 부터는 마지막 칸에 0이 될 수 없기 때문에 가지 않는 방식을 사용.

import sys
input = sys.stdin.readline

N, M = map(int,input().split())

dist = []
for _ in range(N):
    dist.append(int(input()))

# DP 는 시간을 행으로 열은 지침 지수로 사용
# 지침 지수는 0~M까지 가능하기 때문에 M+1까지
dp = [[-1] * (M+1) for _ in range(N)]
# 초기 시작 
# 처음에 움직이거나 쉬거나
dp[0][0] = 0
dp[0][1] = dist[0]

# 시간에 따라서 시작
# 마지막에는 무조건 쉬어야 하기때문에 N-1까지
for i in range(N-1):
    for j in range(M+1):
        # 도착한 적이 있는 dp이면
        if dp[i][j] != -1:
            # 지침지수가 0
            if j == 0:
                # 안 움직일 때
                if dp[i+1][j] < dp[i][j]:
                    dp[i+1][j] = dp[i][j]
                # 움직인다면 비교하고 더 큰 값.
                # 하지만 열과 행의 합이 N이상이면 마지막에 지침지수가 0일수가 없다.
                if (i + 1) + (j + 1) < N and dp[i+1][j+1] < dp[i][j] + dist[i+1]:
                    dp[i+1][j+1] = dp[i][j] + dist[i+1]
            
            # 지침지수가 M 일때(무조건 쉬어야함)
            # 쉴 때는 무조건 지침지수가 0일때 까지기 때문에
            # 사이는 다 건너뛰고 지침지수가 0 일때 시간에 값을 비교
            elif j == M:
                if dp[i+M][0] < dp[i][j]:
                    dp[i+M][0] = dp[i][j]
            
            # 나머지
            else:
                # 안 움직일 때
                if dp[i+j][0] < dp[i][j]:
                    dp[i+j][0] = dp[i][j]
                # 움직일 때
                if (i + 1) + (j + 1) < N and dp[i+1][j+1] < dp[i][j] + dist[i+1]:
                    dp[i+1][j+1] = dp[i][j] + dist[i+1]
                    
# 지침지수가 0이여야 하기 때문에
print(dp[-1][0])