본문 바로가기

알고리즘 관련/BOJ

BOJ)14501 퇴사

문제: icpc.me/14501


i일 부터 일을 할 때 얻을 수 있는 급여의 최댓값으로 DP테이블을 잡으면 쉽게 계산할 수 있는 문제이다.


dp[i]의 점화식은 max(dp[i+1],dp[i+t[i])+p[i]) 가 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, dp[16], t[16], p[16];
int func(int pos) {
    if (pos == n + 1)return 0;
    if (pos > n + 1)return -987654321;
    int &ret = dp[pos];
    if (ret != -1)return ret;
    return ret = max(func(pos + 1), func(pos + t[pos]) + p[pos]);
}
int main() {
    scanf("%d"&n);
    memset(dp, -1sizeof(dp));
    for (int i = 1; i <= n; i++
        scanf("%d%d"&t[i], &p[i]);
    printf("%d\n", func(1));
    return 0;
}
cs


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

BOJ)14503 로봇 청소기  (0) 2017.04.17
BOJ)14500 테트로미노  (4) 2017.04.17
BOJ)14502 연구소  (2) 2017.04.17
BOJ)3079 입국심사  (1) 2017.04.13
BOJ)2820 자동차 공장  (0) 2017.04.13