[백준 14501] 퇴사

안녕하세요 !!! 우디🤓 입니다.

오늘은 DFS로 푸는 퇴사 문제를 설명해드릴께요 ~

 

문제

[백준 14501] 퇴사

 

문제 설명

퇴사 전까지 겹치지 않게 상담을 하면서 최대 수익을 만들어야 합니다. 그러면, 최대 수익을 만들기 위해 최적화로 한번에 똬 !!!상담 일정을 잡을 수 있을까요 ?!

🐿️ : 저는 못할 것 같아요 ~!

녜녜 ~ 저도 그렇게 생각합니다 !

그래서 이 문제는

• 상담일이 겹치지 않게 가능한 경우의 수를 모두 찾은 다음 (순환 DFS 사용)
• 각 경우의 수의 최댓값을 계속 갱신해주면 됩니다 . (새로운 상담일마다 최댓값 갱신)

우선, 상담일이 겹치지 않게 가능한 경우의 수를 트리🌳로 나타내면.

 

 

이렇게 되는데 이런 경우의 수를 구하는 방식을 저는 순환구조의 DFS 로 해결하였습니다.

위의 예로 간단히 설명을 하자면, 1일, 4일, 5일 일하고 7일까지 가서 더 이상 일할 수 없죠 ? 이 상태에서 다시 5일째로 돌아가고 ... 쭉쭉 이런 식으로

또한, 새로운 상담일을 잡을때마다 최댓값(최종 답)을 갱신해줘야 합니다.

 

구현

x
#include <iostream>
using namespace std;
​
int arr[20][20];
int n;
int ans = 0;//답
int maxx = 0;
​
void dfs(int num);
​
int main()
{
    int ti, pi;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> ti >> pi;
        arr[0][i] = ti;
        arr[1][i] = pi;
    }
​
    for (int i = 0; i < n; i++)
        dfs(i);//처음 시작을 달리하여 dfs 돔.
    cout << ans;
}
​
void dfs(int num)
{
    if ((num + arr[0][num] - 1) >= n)
        return;
    else
    {
        maxx += arr[1][num];
        if (maxx > ans) ans = maxx;
        for (int i = num + arr[0][num]; i < n; i++)
            dfs(i);
        maxx -= arr[1][num];//for문이 끝나면 전으로 돌아가기 위해 자기자신 수익을 빼줌.
    }
}

 

어려운 점 및 개선점

솔직히 어렵지는 않았다. 이런 문제가 실제로 삼성 시험치러 갔는데 나온다면 ,,,,,, 너무 행복할 것 같다.