[Algorithm] 백준 14501번 퇴사

백준 14501번 퇴사

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

굉장히 쉬운 이유는 간절하게 퇴사를 바라기 때문 일수도 있음 ㅋ

문제 풀이

완전탐색으로 첫날을 기반으로 그 날 상담을 한다/안한다로 쭉쭉 이어나가면 됩니다.

그리고 그 중간 중간에 가장 큰 수입을 얻은 날의 금액을 answer로 저장하면 됨.

사람마다 다르겠지만, 저는 yes/no 로직을 코드로 짤 때는 dfs로 사용합니다.

이전 문제에서도 그랬지만, 재귀에서 yes인 경우와 no인 경우를 둘 다 호출하면 됩니다.

dfs라는 네이밍을 하는 이유는 그냥 옛날부터 해온 습관이고 빠르게 칠 수 있기 때문임.

맨 밑의 전체 소스 코드의 Lin 13~20 부분은 아래와 같습니다.

dfs 함수의 parameter로는 day, sum이 있음

- day : 오늘 몇 번째 날인지 (ex day = 0 이면, 첫 번째날)

- sum : 현재 날까지 수익

1 2 3 4 5 6 7 8

void dfs(int day, int sum) {     if (sum > answer && day <= N) {         answer = sum;     }     if (day >= N) return;     dfs(day + time[day], sum + profit[day]);     dfs(day + 1, sum); } Colored by Color Scripter

cs

dfs(day + time[day], sum + profit[day])

- time[day] (오늘 상담이 걸리는 일수) 

- profit[day] (오늘 상담으로 벌게 될 수익) 

- 위의 2개 값을 parameter에 더하여 전달하여 줌으로써 그 날 상담을 진행했다는 것을 의미함.

dfs(day + 1, sum)

- 1을 더함으로써 그 날 상담을 진행하지 않고, 다음 날로 넘어가겠다는 의미

- 그 날 상담을 진행하지 않았기 때문에, 수익에도 변화가 없으므로 sum을 그대로 넘겨줌.

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int N;
int time[16];
int profit[16];
 
int answer = 0;
void dfs(int day, int sum) {
    if (sum > answer && day <= N) {
        answer = sum;
    }
    if (day >= N) return;
    dfs(day + time[day], sum + profit[day]);
    dfs(day + 1, sum);
}
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> time[i] >> profit[i];
    }
    dfs(0, 0);
    cout << answer;
    return 0;
}