티스토리 뷰

알고리즘 관련/BOJ

BOJ)2419 사수아탕

JASON 자손9319 2017. 8. 27. 00:24

문제:icpc.me/2419


사탕이 담긴 사탕바구니가 x축위에 있고 1초마다 사탕 바구니의 사탕이 1개씩 사라질 때 수아가 먹을 수 있는 최대의 사탕 수를 구하는 문제이다.


문제가 다이나믹 프로그래밍임은 쉽게 알 수 있었지만 먹을 수 있는 최대의 사탕수에 포커스를 맞추니 어려워진 문제였다.


이를 dp[l][r][state]로 해결해야하는데 l에서 r까지 사탕을 커버하고 state(왼,오)에 서있을 때 먹는 최대의 사탕수라고 


정의를 한 뒤 제출을 하니까 WA를 받았다. 다시 잘 생각해보니 l~r을 커버할 때 나머지 구간에 사라진 사탕수가 항상 최적으로 있을 수 없다는 걸 깨달았다.


따라서 dp테이블의 정의를 바꾸어 l에서 r까지 구간을 커버하고 사라지는 사탕 수로 문제를 풀어야한다.


근데 이 또한 사라지는 사탕수를 계산하기 어려워지기 때문에 먹을 사탕 K를 정해놓고 모든 k에 대하여 답을 구해보면 된다.


K를 정한다면 예를 들어 현재 먹을 사탕이 k개 남았고 l~r까지 커버하고 r에서 r+1로 이동한다면 (a[r+1]-a[r])*k 개의 사탕이 사라질것이다.(이동하는 동안 앞으로 먹을 나머지 k개의 사탕이 사라지기 때문)


이를 이용하여 점화식을 세워준 뒤 풀면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int n, dp[333][333][2], x, m, res;
vector<int> v;
int func(int l, int r, int state, int rem) {
    if (!rem)return 0;
    if (l > r)return 1e9;
    int &ret = dp[l][r][state];
    if (ret != -1)return ret;
    ret = 1e9;
    if (state) {//왼
        if (r != n)
            ret = min(ret, func(l, r + 10, rem - 1+ rem*(v[r + 1- v[l]));
        if (l)
            ret = min(ret, func(l - 1, r, 1, rem - 1+ rem*(v[l] - v[l - 1]));
    }
    else {//오
        if (r != n)
            ret = min(ret, func(l, r + 10, rem - 1+ rem*(v[r + 1- v[r]));
        if (l)
            ret = min(ret, func(l - 1, r, 1, rem - 1+ rem*(v[r] - v[l - 1]));
    }
    return ret;
}
int main() {
    scanf("%d%d"&n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d"&x);
        v.push_back(x);
    }
    v.push_back(0);
    sort(v.begin(), v.end());
    memset(dp, -1sizeof(dp));
    int idx = lower_bound(v.begin(), v.end(), 0- v.begin();
    for (int i = 0; i <= n; i++) {
        memset(dp, -1sizeof(dp));
        res = max(res, i*- func(idx, idx, 0, i));
    }
    printf("%d\n", res);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1460 진욱이의 농장  (0) 2017.09.05
BOJ)13548 수열과 쿼리 6  (0) 2017.09.03
BOJ)2419 사수아탕  (0) 2017.08.27
BOJ)2370 시장 선거 포스터  (1) 2017.08.21
BOJ)3073 집으로 가는 길  (0) 2017.08.21
BOJ)2104 부분배열 고르기  (0) 2017.08.20
댓글
댓글쓰기 폼