[C++] 백준 14501번: 퇴사

🔗 문제

14501번: 퇴사

14501번: 퇴사

 

🖍 풀이

 

일을 했을 경우와 일을 하지 않았을 경우로 상황을 나눠 생각할 수 있다.

• i 날에 일을 한 경우: i + T[i] 에 수익이  전에 벌어 놓은 돈 + P[i] 이 된다.
• i 날에 일을 하지 않을 경우: i+T[i]날 수익에 변동이 없다.
•  

이걸 재귀함수로 짠다면?

간단하게 생각하면 완전 탐색할 수 있다.

void solve(int days, int profit)
{
    if(days == N+1)
    {
        return;
    }
    
    solve(days + T[days], profit + P[days]);
    solve(days + 1, profit)
}

하지만 재귀함수는 호출된 함수 메모리가 스택에 쌓인다.

메모리를 더 효율적으로 사용하기 위해 동적 프로그래밍의 개념을 도입해 풀 수 있다.

 

i날의 최대 이익을 저정할 DP라는 배열을 생성한다.

일을 했을 때 수익이 발생하는 날은 일이 끝난 다음날이다. 그래서 DP배열을 N+1 크기만큼 생성하고, 반복문도 i≤N로 실행한다.

 

그리고 아까 나눠 본 상황을 코드로 표현한다.

• i 날에 일을 한 경우: i + T[i] 에 수익이  전에 벌어 놓은 돈 + P[i] 이 된다.
• i 날에 일을 하지 않을 경우: i+T[i]날 수익에 변동이 없다.

DP[day + T[day]] = std::max( 전에 벌어 놓은 돈 + P[day], DP[day + T[day]]);

 

💾  소스

동적 프로그래밍

#include <iostream>
#include <algorithm>

int N, answer = 0;
int T[100] = {0, };
int P[100] = {0, };
int DP[100] = {0, };
	
int main()
{
	std::cin >> N;
	for(int i=0; i<N; ++i)
		std::cin >> T[i] >> P[i];

	for(int day=0; day<=N; ++day)
	{
		answer = std::max(answer, DP[day]);

		if(T[day] + day <= N)
			DP[day + T[day]] = std::max(answer + P[day], DP[day + T[day]]);
	}

	std::cout << DP[N];

	return 0;
}

완전 탐색ver

#include <iostream>
#include <algorithm>
const int MAX = 1001;
int N, answer = 0;
int T[MAX] = {0, }, P[MAX] = {0, };

void solve(int days, int profit)
{
    if(days == N)
    {
        answer = std::max(answer, profit);
        return;
    }
    
		//days에 배당받은 일 안하고 다음날 일 확인
    solve(days+1, profit);

    if(days+T[days] <= N) // 퇴사일만 넘지 않는다면 일 접수
        solve(days+T[days], profit + P[days]);

}
int main()
{
    std::cin >> N;
    for(int i=0; i<N;++i)
    {
        std::cin >> T[i] >> P[i];
    }

    solve(0, 0);
    std::cout << answer;
    
    return 0;
}