[Inflearn] 휴가(삼성 SW역량평가 기출 - DFS) (c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

    - N일동안 최대한 많은 상담

    - 최대 이익이 나는 스케쥴

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

	1일	2일	3일	4일	5일	6일	7일
T	4	2	3	3	2	2	1
P	20	10	15	20	30	20	10

모든 경우의 수를 확인해야하지만 상담이 걸리는 일수와,

해당 날짜에 상담을 시작해야하는 조건이 있다.

우선 1일부터 7일까지 할 수 있는 스케쥴을 모두 잡아보자.

1일 스케쥴을 할 수 있다면, 4일 후에 새로운 스케쥴을 진행할 수 있다.

괄호는 새로운 스케쥴을 진행할 수 있는 날짜라고 생각하자.

스케쥴	1일(5일) ->
금액	20 +

다음으로 5일 스케쥴을 잡는다면, 2일 뒤에 새로운 스케쥴을 진행할 수 있다.

스케쥴	1일(5일) -> 5일(7일)
금액	20 +  30 +

다음으로 7일 스케쥴을 잡는다면, 1일 뒤에 새로운 스케쥴을 진행할 수 있다.

스케쥴	1일(5일) -> 5일(7일) -> 7일(8일)
금액	20 +  30 + 10

총 수익은 60이 된다.

이 값을 max 변수에 저장해두고, 

다른 경우도 생각해본다.

5일 스케쥴을 마치고 해볼수 있는 스케쥴은 7일 스케쥴밖에 없으므로 pass

1일 스케쥴을 마지고 해볼수 있는 스케쥴은 5일 스케쥴 말고 6일 스케쥴일수도 있다.

스케쥴	1일(5일) -> 6일(8일)
금액	20 +  20

총 수익은 40으로 60보다 작다.

이번에 1일 스케쥴을 소화하고 할 수 있는 경우를 모두 보았으니, 

2일 스케쥴을 소화하고 할 수 있는 스케쥴을 보자.

스케쥴	2일(4일) ->
금액	10 +

2일 스케쥴을 마치고 4일 스케쥴을 해보자.

스케쥴	2일(4일) -> 4일(7일)
금액	10 + 20

4일 스케쥴을 마치고 7일 스케쥴을 진행할 수 있다.

스케쥴	2일(4일) -> 4일(7일) -> 7일(8일)
금액	10 + 20 + 10

마찬가지로 총 수익은 40으로 60보다 작다.

이런 과정으로 재귀함수를 계속 호출해보면서 가능한 모든 경우의 수를 확인해보자.

#. Code

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define t first
#define p second
#define MAX 2147000000
#define MIN -2147000000
 
int n, cost = 0, income = MIN;
vector<pair<int, int> > vt(16);
 
void DFS(int day, int cost)
{
    int i;
 
    if (day > n)
    {
        if (cost > income)
            income = cost;
    }
    else
    {
        for (i = 1; i <= n; i++)
        {
            if (day <= i)
            {
                if (i + vt[i].t > n + 1)
                {
                    DFS(i + vt[i].t, cost);
                    return;
                }
 
                DFS(i + vt[i].t, cost + vt[i].p);
            }
        }
    }
}
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int i, a, b;
 
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        scanf("%d %d", &a, &b);
        vt[i] = { a, b };
    }
 
    DFS(0, 0);
 
    printf("%d\n", income);
 
    return 0;
}

line 14~39) 현재 날짜와 비금까지의 수입을 인자로 받음

line 18~22) 날짜가 휴가 출발날인 n+1을 넘어간다면 그 당시의 수입을 저장(최댓값일 경우)

line 23~38) 1일부터 n일까지 가능한 일자를 탐색

line 27~36) 현재 날짜 이후의 스케쥴이라면 이후의 스케쥴을 일정에 넣어본다.(line 35)

line 29~33) 만일, 스케쥴에 넣어봤는데 휴가 출발날인 n+1보다 크다면 비용은 그대로 유지하고

     line 18에서 종료를 위해 넘겨준다. 그러고 return

     이 부분에서 많이 헤맸었는데, 디버깅하면서 코드를 고쳐가다보니까 뭔가 효율적이지 않은 코드가 

     된 것 같다.. 

#. Other code

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int n, res = -2147000000;
vector<int> T, P;
 
void DFS(int L, int sum) {
    if (L == n + 1) {
        if (sum > res) 
            res = sum;
    }
    else {
        if (L + T[L] <= n + 1) 
            DFS(L + T[L], sum + P[L]);
 
        DFS(L + 1, sum);
    }
}
 
int main() {
    freopen("input.txt", "rt", stdin);
 
    int i, a, b;
 
    T.push_back(0);
    P.push_back(0);
 
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++)
    {
        scanf("%d %d", &a, &b);
 
        T.push_back(a);
        P.push_back(b);
    }
 
    DFS(1, 0);
 
    printf("%d\n", res);
 
    return 0;
}

이렇게나 간단하게 짤 수 있는 문제였는데,,, 현타가 온다.. 하핳..

더 분발하자ㅠㅠ

line 28~29) vector 를 1번 idx부터 사용하기 위해 0번 idx에 0으로 그냥 채워준 것이다.

line 10~21) 마찬가지로 현재 날짜와 현재 수입을 인자로 받는다

line 11~14) 날짜가 휴가 출발날인 n+1이라면 재귀호출을 중단한다.

               여기서 수입이 최대라면 저장

line 15~20) 

line 16~17) 현재 날짜에서 다음 스케쥴을 진행할 경우 날짜의 합이,

               휴가 출발일보다 작거나 같다면 스케쥴을 진행해도 되므로, 재귀함수를 호출

line 19) 해당 스케쥴을 진행하지 않을 경우, 

     날짜를 다음날로 올리고, 수입도 그냥 넘겨준다.

내 코드와 비교했을 때,,

모든 날짜를 다 확인해볼 필요가 없었다.

그냥 단순하고 간단하게 해당 스케쥴을 진행할지 안 할지를 나눈 후,

스케쥴을 진행할 경우의 조건만 설정해주었다면 쉽게 해결해낼 수 있었는데..

다시 한 번 정리해보면,

이번 문제에서 포인트는

1. 휴가 출발날짜가 되었을 떄, 재귀함수 종료

2. 해당 스케쥴을 진행할지 안 할지 나누기

3. 해당 스케쥴을 진행할 경우, 휴가 출발일을 넘어설 수 없도록 조건이 필요. 

DFS 문제를 많이 풀어보면서 더 익숙해져야 할 필요가 있다..

#. Result

  - Input --------------------------------------------------------

7 

4 20 

2 10 

3 15 

3 20 

2 30 

2 20

1 10

------------------------------------------------------------------

  - Output --------------------------------------------------------

60

------------------------------------------------------------------