티스토리 뷰

알고리즘 관련/BOJ

BOJ)2662 기업투자

JASON 자손9319 2017. 2. 3. 03:55

문제: icpc.me/2662


투자 가능금액과 기업의 수가 주어지고 해당 기업에 x원만큼 투자했을 때 얻을 수 있는 이득 y가 주어질 때 최대 이익을 출력하는 문제이다.


최대 이익은 다이나믹 프로그래밍을 통하여 구해줄 수 있다. 


테이블 dp[val][pos]의 정의는 "val 만큼 투자 가능할 때 pos번째 기업부터 n번째 기업까지 투자하여 얻을 수 있는 최대 이익"이 될것이다. 4


점화식은 dp[val][pos] = for(i=1~k) max(dp[val-i][pos+1]+a[i][pos]) 가 될것이다. 여기서 a[x][y]는 y번째 기업에 x만원을 투자하여 얻을 수 있는 돈이다.


이 때 역추적을 해주기 위하여 최댓값의 갱신이 일어날 때 마다 역추적 배열을 갱신해준 뒤 함수 종료후 백트래킹 해주면 된다.


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
#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 987654321
using namespace std;
int k, n, x, y, z;
int a[301][21];
int dp[301][21];
pair<intint> back[301][21];
int func(int val, int pos) {
    if (val == 0)
        return 0;
    if (pos > n)
        return -INF;
    if (val < 0)
        return -INF;
    int &ret = dp[val][pos];
    if (ret != -1)return ret;
    for (int i = 0; i <= k; i++) {
        if (ret < func(val - i, pos + 1+ a[i][pos]) {
            ret = func(val - i, pos + 1+ a[i][pos];
            back[val][pos] = { val - i,pos + };
        }
    }
    return ret;
}
int main(){
    memset(dp, -1sizeof(dp));
    scanf("%d%d"&k, &n);
    while (scanf("%d"&x) != EOF) {
        for (int i = 1; i <= n; i++)
            scanf("%d"&a[x][i]);
    }
    printf("%d\n", func(k, 1));
    x = k, y = 1;
    for (int i = 1; i <= n; i++) {
        printf("%d ", x - back[x][y].first);
        int cx = x;
        x = back[x][y].first;
        y = back[cx][y].second;
    }
    return 0;
}
cs


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

BOJ)9202 Boggle  (0) 2017.02.04
BOJ)5052 전화번호 목록  (0) 2017.02.03
BOJ)2662 기업투자  (0) 2017.02.03
BOJ)9252 LCS 2  (0) 2017.02.02
BOJ)1701 Cubeditor  (0) 2017.02.01
BOJ)11585 속타는 저녁 메뉴  (0) 2017.02.01
댓글
댓글쓰기 폼