백준 1757 달려달려

1757번: 달려달려

문제

어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정확히 N분에 완주할 수 있는 시간 안배능력까지 갖추게 되었다.

그래서 N분동안 학생들은 달릴지 아님 쉴지 결정하여야 한다. 그러나 학생들도 인간이기 때문에 계속 달릴 수는 없다. “지침 지수”라는 것이 있어서 1분을 달린다면 “지침 지수”는 1이 올라간다. 반대로 1분을 쉰다면 “지침 지수”는 1이 내려간다. 또한 이 “지침 지수”가 M보다 커지면 학생들은 더 이상 달릴 수가 없다.

아주 특이하게도 학생들은 시간에 따라 달릴 수 있는 거리가 다르다. 만약 I분에 달렸다면 Di 만큼의 거리를 달릴 수 있다. (i분을 달렸다는 것이 아니라 I분이 되는 때에 달렸다는 뜻임) 또한 학생들이 쉬기 시작하면 지침지수가 0이 되기 전에는 다시 달릴 수가 없다.

물론 이 달리기가 끝나면 학생들은 다시 공부를 해야한다. 그렇기 때문에 달리기가 끝난다음 지침지수가 0이 되지 않는다면 맑은 정신으로 문제를 풀 수가 없기 때문에 달리기가 끝나면 지침지수는 0이 되어야 한다.

월드학생들이 최대한 멀리 갈 수 있는 거리를 구해보자.

풀이

냅색으로 풀었다.

1. 지침지수가 0인 경우 -> 다시 달리거나 한번 더 쉴 수 있다.

2. 지침지수가 0이 아닌 경우 -> 지침지수가 M이 되기 전까지 한번 더 뛰거나 지침지수가 0이 될때까지 쉰다.

3. 지침지수가 M인 경우 -> 무조건 지침지수가 0이될때까지 쉬어줘야한다.

수업 시작하기 전에 무조건 지침지수가 0이 되어야 하므로 달리기가 끝난 다음에 지침지수가 0보다 크다면 -9999999 값을 반환해서 답이 될 수 없게 했다.  처음에는 수업시작하기 전에 무조건 지침지수가 0이 되어야 하므로 if(pos==N-M) 이면 return 0; 이런식으로 코딩했는데 아래와 같은 반례가 있었다ㅎ

input

4 2

1

5

2000

3

ouput

2001

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N, M;
vector<int> d;
int dp[10001][501];
 
int knapsack(int pos, int m) 
{
    if (pos == N - m) return 0;    // 수업 시작하기 전에 무조건 지침지수가 0이 되어야함
    if (pos > N - m) return -99999999;
    if (dp[pos][m] >= 0) return dp[pos][m];
    int ret = 0;
    if (m < M) {    // 지침지수가 M보다 작으면 더 달릴 수 있음
        if (m > 0) {
            ret = max(knapsack(pos + 1, m + 1) + d[pos], knapsack(pos + m, 0));
        }
        else if (m == 0) {    // 지침지수가 0이면 다시 뛰거나, 한번 더 쉴 수있음
            ret = max(knapsack(pos + 1, m + 1) + d[pos], knapsack(pos + 1, 0));
        }
    }
    else if (m == M) {    // 지침지수가 M이면 무조건 M번 쉬어서 지침지수를 0으로 만들어줘야함
        ret = knapsack(pos + m, 0);
    }
 
    return dp[pos][m] = ret;
}
 
int main(void)
{
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        d.push_back(a);
        fill(dp[i], dp[i] + M + 1, -1);    // dp배열을 -1로 초기화
    }
    
    cout << knapsack(0, 0) << "\n";
 
    return 0;
}