[BOJ] 14501번 퇴사 문제풀이 (C++)

2017.10.4 에 작성된 글 입니다.

---

문제링크

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

14501번: 퇴사

 

풀이방법

DP로 푸는데 .. 주석 참고...

 

소스코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N;
int T[16];        //기간저장
int P[16];        //비용저장
int dp[17];
 
void Init()
{
    for (int i = 1; i <= N; i++) {
        T[i] = 0;
        P[i] = 0;
        dp[i] = 0;
    }
    dp[N + 1] = 0;
}
 
int main()
{
    cin >> N;
    Init();        //초기화
    for (int i = 1; i <= N; i++)
        cin >> T[i] >> P[i];
    dp[0] = 0;
    for (int i = 1; i <= N + 1; i++)
        for (int j = 1; j <= i; j++)
            if (i - j >= T[j])            //i일에서 j일전으로 돌아가서 j일에 해당하는 일을 맡을수있으면
                dp[i] = max(dp[j] + P[j], dp[i]);    //일 맡고 현재 i일과비교 
    cout << dp[N + 1] << endl;            //퇴사일에 받는 비용 출력
 
    return 0;
}

 

참고

2017년 상반기 삼성전자 CE/IM 기출 문제

테트로미노랑 퇴사문제가 같이 나왔음.