문제

문제 링크

문제 접근

  • 이 문제는 디피를 이용해서 풀면 쉽게 해결할 수 있는 문제이다.
  • 첫 날부터 마지막 날까지 하나하나 값을 갱신하면서 마무리한다.
  • 상담 기간 최대 5일 이기 때문에 각 날짜에 대해서 1,2,3,4,5일 전에 상담을 시작한 내역이 있다면 해당 날짜의 금액에 상담비용을 더한다. 이때 1~5일전 값 중에 제일 큰 친구를 해당 날짜의 값으로 갱신한다.

코드

#include <cstdio>

int n, t[16], p[16], v[16];
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++)scanf("%d %d", &t[i], &p[i]);
    for(int i = 1; i < n + 1; i++){
        v[i] = v[i-1];
        for(int j = 1; j < 6; j++){
            if(i - j < 0 || j != t[i - j])continue;
            if(v[i] < v[i - j] + p[i - j])v[i] = v[i - j] + p[i - j];
        }
    }
    printf("%d", v[n]);
}

느낀점

  • 디피굳 ㅎㅎ