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

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

 

모든 직장인들의 가슴속에 담긴 단어

"퇴사"

짜자자잔

 

흠

 

쉽다쉬워

 

문제는 대충 이해가 갈 것이다

 

1일차에 3일되는 상담을 받으면

비용 10 받고

3일동안 못하니까

 

4일부터 시작하고... 이걸 n일까지 할 수 있는거잖아

 

n은 최대 15에다가, 시간은 2초나 주네?

>>모든 경우의수 ㄱㄱ

 

>>백트래킹 ㄱㄱ

대충 위에 그려진 표를 보고 흐름을 적으면 이렇게 되겠지?

 

그리고 만약 6일차로 갔을 땐 t=2이고, 이 경우는 안되겠군.. 다시 뒤로 돌아가! backtracking

 

코드로 ㄱㄱ

 

#include <iostream>

#include <cmath>

#include <algorithm>

using namespace std;

int arr[15][2];

int sum = 0;

int temp_max = 0;

void task(int depth, int n);

int main()

{

    int n;

    cin >> n;

    for (int i = 0; i < n; i++)

    {

        cin >> arr[i][0] >> arr[i][1];

    }

    task(0, n);

    cout << temp_max << "\n";

}

void task(int depth, int n)

{

    if (depth > n)

        return;

    if (depth == n)

    {

        temp_max = max(temp_max, sum);

        return;

    }

    while (depth <= n)

    {

        sum += arr[depth][1];

        task(depth + arr[depth][0], n);

        sum -= arr[depth][1];

        depth++;

    }

}

앞선 수열 문제들하고 굉장히 유사함을 볼 수 있다.

하지만 다른점이 있다면

 

  while (depth <= n)

    {

        sum += arr[depth][1];

        task(depth + arr[depth][0], n);

        sum -= arr[depth][1];

        depth++;

    }

이것일 것이다.

 

i를 하나씩 증가시키는 경우는 , 원소의 갯수가 n인 "모든 수열"을 확인할 때 지만, 이건 가용 날짜에 따라, 수용할 수 있는 날이 각각 달라지지 않겠는가?

 

그러니까 depth를 날짜만큼 추가해주는 것이지~