[ 백준 14501 ] 퇴사 (C++)

백준의 퇴사(14501) 문제이다.

[ 문제 바로가기 ]

삼성전자 SW 역량테스트 기출문제이다..

[ 문제풀이 ]

1) 이 문제는 2가지 방법으로 풀 수가 있다. 먼저, Dynamic Programming으로 해결하는 방법이 있고, 완전탐색(BruteForce)로 해결할

   수 있다. 본인은 N의 값이 너무 크지 않기 때문에, 완전탐색으로 해결하였다.

   먼저, 상담을 하는데에는 크게 2가지 방법이 있다.

   1. 해당 날에 상담을 하지 않고, 그 다음날로 넘어가는 방법.

   2. 해당 날에 상담을 하고, 해당 상담을 하는데 걸리논 총 일수 만큼 넘어가는 방법

   이렇게 2가지 방법이 있다.

   본인은 이 부분을 재귀를 통해서 구현해주었다. 매개변수에는, 현재 날짜와 지금 까지의 금액 이 2개의 변수를 가져와서

   계속 관리해주었다.

  

   종료조건은 현재 날짜가 N+1보다 크거나 같으면 종료를 시켜주었다. N보다 크거나 같다고 할 경우, N번째 날에 있는 상담을

   하고 버는 돈이 계산이 안될 수 있으니 이 부분 주의해주자.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 16
using namespace std;
 
int N;
int Day[MAX];
int Cost[MAX];
 
int Answer;
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Day[i] >> Cost[i];
    }
}
 
void DFS(int Cur_Day, int Total_Cost)
{
    if (Cur_Day >= N + 1)
    {
        Answer = Bigger(Answer, Total_Cost);
        return;
    }
 
    if (Cur_Day + Day[Cur_Day] <= N + 1) DFS(Cur_Day + Day[Cur_Day], Total_Cost + Cost[Cur_Day]);
    // 해당날에 상담을 하고, 해당 상담을 하는데 걸리는 총 일수 만큼 넘어가는 방법
    if (Cur_Day + 1 <= N + 1) DFS(Cur_Day + 1, Total_Cost);
    // 해당날에 상담을 하지 않고, 그 다음날로 넘어가는 방법(Day가 +1만됨)
}
 
void Solution()
{
    DFS(1, 0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}