[C++] 2419번 사수아탕 - DP

2419번 사수아탕

1. 문제

• 수아는 0에서 출발하여 시간 1마다 x축을 따라 1만큼 움직인다. 수평선에는 n개의 바구니가 있고 각 바구니에는 m개의 사탕이 들어있다. 각 바구니는 \(x_1, x_2, ..., x_n\)에 있다. 사탕을 다 먹는데 0의 시간이 걸린다. 1만큼 시간이 지나갈 때 사탕은 녹아 1만큼 줄어든다. 먹을 수 있는 사탕의 최대 개수를 출력하라.

<입력>

• -1-   \(n, m(0 \leq n \leq 300, 1 \leq m \leq 1,000,000)\)
• -n-   \(x_i(-10,000 \leq x_i \leq 10,000) (x_i \neq x_j)\)

<출력>

• -1-   수아가 먹을 수 있는 사탕의 최대 개수

2. 재정의

• X

3. 해결 방법

• l번째 사탕을 먹기 위해선 l+1번째 사탕을 먼저, r번째 사탕을 먹기 위해선 r-1번째 사탕을 먼저 먹어야 한다.
• dp[l][r]처럼 설정하고 이를 지금까지 먹은 사탕을 개수라고 하면 현재 위치와 시간을 추가로 고려해야 하고 이는 쉽지 않다. 따라서 역방향으로 dp를 세우는 것이다. 나는 k개를 먹을 예정이고 dp[l][r][k]는 k를 먹을 때까지 녹은 사탕의 개수이다. 녹은 사탕의 개수를 총 사탕의 개수에서 빼면 먹은 사탕의 개수를 얻을 수 있고 아래와 같이 dp를 짜면 시간을 고려하지 않아도 된다.

• 처음 해결 방법은 아래 블로그 글을 읽고 힌트를 얻었다.

4. 실수한 점, 개선할 점

• X

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

const int MAX_N = 300;
const int MAX = 987654321;

// <문제>
// 사탕 바구니의 개수 N, 사탕의 개수 M
int N, M;
// 사탕 바구니의 위치 X[i]
vector<int> X;

// <DP>
int dp[MAX_N][MAX_N][2];

void input() {
    cin >> N >> M;
    for(int i=0; i<N; i++) {
        int x;
        cin >> x;
        X.push_back(x);
    }
    X.push_back(0);
}

int func(int l, int r, int lr, int k) {
    // 목표한 개수만큼 다 먹은 경우
    if(!k)
        return 0;
    if(l > r)
        return MAX;
    int &ret = dp[l][r][lr];
    if(ret != -1)
        return ret;
    
    ret = MAX;
    // 오른쪽
    if(lr) {
        if(r != N)
            ret = min(ret, func(l, r+1, 1, k-1) + k*(X[r+1] - X[r]));
        if(l)
            ret = min(ret, func(l-1, r, 0, k-1) + k*(X[r] - X[l-1]));
    }
    else {
        if(r != N)
            ret = min(ret, func(l, r+1, 1, k-1) + k*(X[r+1] - X[l]));
        if(l)
            ret = min(ret, func(l-1, r, 0, k-1) + k*(X[l] - X[l-1]));
    }
    
    return ret;
}

void solve() {
    sort(X.begin(), X.end());
    // 원점의 위치
    int zeroloc = lower_bound(X.begin(), X.end(), 0) - X.begin();
    
    int res = 0;
    for(int i=1; i<=N; i++) {
        memset(dp, -1, sizeof dp);
        res = max(res, i*M - func(zeroloc, zeroloc, 0, i));
    }
    
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    solve();
    
    return 0;
}

 

<문제 바로가기>

https://www.acmicpc.net/problem/2419

2419번: 사수아탕

 

<힌트를 얻은 글>

https://egod1537.tistory.com/entry/BOJ-2419-%EC%82%AC%EC%88%98%EC%95%84%ED%83%95

[백준 2419] 사수아탕

 

 

※ 궁금한 것 질문 남겨주시면 답변드리겠습니다. 좋아요 눌러주시고 편하게 질문해 주세요.