[백준/c++] 14501번: 퇴사

 

 

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

14501번: 퇴사

 

 

n일 동안 일을 하는데, 백준이가 얻을 수 있는 최대 수익은 얼마인지 구하는 프로그램을 작성하면 된다.

완전 탐색과 dp 중 하나를 선택하면 된다. n이 15 이하이므로 완전 탐색도 가능하다. 근데, dp 연습을 하고 싶어서 dp로 해봤다. 규칙 찾는게 생각보다 어려웠다.. 하나의 예시를 잡고 막일(..)을 하면 나름 잘 보이는데 뭔가 너무 꼬아서 생각해서 오히려 독이 되었다. 흑흑

 

1일부터 n일까지 각 날짜까지만 일을 한다면 구할 수 있는 최대 수익을 구하고 dp배열에 넣고 모두 구하면 max value를 구하면 된다. dp는 이전에 구해놨던 값에 추가적으로 자신을 더하는 등의 행동을 하면 되기 때문에 반복문을 통해서 진행했다.

 

i번째 날의 최대수익을 찾을 때는 그 전의 날짜에도 상담을 했을 수도 있기 때문에 반복문을 통해 그 전날(0~i-1)의 dp도 확인하고 dp [i]를 업데이트해준다. 이때, 기간이 i를 넘기지 않는지 && i일의 상담이 퇴사 날을 넘기지 않는지를 확인해줘야 한다.

 

scheduled [i][0] = i일의 상담 기간

scheduled [i][1] = i일의 상담 비용

 

#include <iostream>
#include <algorithm>
#define num 17
using namespace std;
int n, scheduled[num][2], dp[num];

void input(){
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> scheduled[i][0] >> scheduled[i][1]; //duration, payment
    }
}

void solution(){
    int answer = 0;
    for(int i=1; i<=n; i++){
        for(int j=0; j<i; j++){     //숫자의 합 i는 i 보다 작은 값으로 이루어지므로 (j: 1, 2, ... , i-1)
            if(scheduled[j][0] + j <= i && scheduled[i][0] + i <= n+1)
                dp[i] = max(dp[i], dp[j] + scheduled[i][1]);
        }
    }
    for(int i=1; i<=n; i++) answer = max(dp[i], answer);
    cout << answer << '\n';
}

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

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!