[백준/C++] 알고리즘 14501번 - 퇴사1

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘14501번 - 퇴사 를 풀어보도록 하겠습니다.

 

 

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

14501번: 퇴사

 

[문제 접근]

시간제한은 2초이고 N은 15이하이기 때문에 완전탐색이 가능합니다. 상담기간을 텀으로 상담을 하기 때문에 DFS로 접근했습니다.

이후에 다이나믹프로그래밍으로도 풀 수 있다고하여 시도했습니다. 그렇지만 만약 시험장에서 이 문제를 마주쳤다면 다이나믹프로그래밍보다 DFS로 먼저 떠오를 거 같네요.

 

[풀이 전략]

 

DFS 풀이

1. dfs 함수를 생성합니다.

- 만약 cnt가 n이면 지금까지의 상담 금액과 최대 상담 금액을 비교하여 최대 상담 금액을 업데이트 합니다.

- 현재 일자와 상담 걸리는 시간의 합이 n보다 작으면  dfs(현재일자 + 상담 걸리는 시간 + 1)을 호출합니다.

- dfs(cnt + 1)을 호출합니다.( 현재 일자와 상담 걸리는 시간의 합이 n과 같거나 큰 경우 + 그냥 건너 뛰는 경우)

2. for문을 이용하여 각 일자를 시작으로 dfs를 호출한다.

 

다이나믹 프로그래밍 풀이

일자순으로 점점 쌓여가고 경우의 수도 줄어드는 형태이기 때문에 거꾸로 접근해야 수월합니다.

역일자순으로 접근하면 가장 작은 문제부터 접근할 수 있고 이 작은 문제를 이용하여 더 큰 문제를 풀 수 있습니다.

1. 점화식을 정의합니다

- dp[i] :  i번째 일에 상담을 시작했을 때 얻을 수 있는 최대 수익

2. 역일자순으로 접근하면서 현재날짜 + 상담 걸리는 시간의 합이 n보다 작거나 같으면 d[i+1](i일에서 상담안하고 하루 넘기는 경우)과 d[i+t[i]]+p[i](i일에 상담하고 상담 이후로 넘어가는 경우)를 비교하여 큰 값으로 d[i]를 업데이트합니다.

3. 그렇지 않다면 d[i]는 d[i+1]로 업데이트합니다.

 

[코드]

BFS 풀이

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int t[16];
int p[16];
int tempTot;
int maxTot;
int n;
void dfs(int cnt) {
  if (cnt == n) {
    maxTot = max(tempTot, maxTot);
    // tempTot = 0 ;
    return;
  }
  if (t[cnt] + cnt < n) {
    tempTot += p[cnt];
    dfs(cnt + t[cnt] + 1);
    tempTot -= p[cnt];
  } 
  dfs(cnt + 1);

}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a;
    int b;
    cin >> a >> b;
    t[i] = a - 1;
    p[i] = b;
  }

  for (int i = 0; i < n; i++) {
    dfs(i);
  }

  cout << maxTot;
}

 

다이나믹 프로그래밍

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


int n ; 
int d[16];
int t[16];
int p[16];

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n ;
    
    for(int i = 0 ; i < n ; i++){
        int a; int b ;
        cin >> a >> b;
        t[i] = a ;
        p[i] = b ;
    }

    for(int i = n-1 ; i >= 0 ; i--) {
        if(i + t[i] <= n) {
            d[i] = max(d[i+t[i]]+p[i], d[i+1]);
        }
        else d[i] = d[i+1];
      
    }
    cout << *max_element(d,d+n);
}

 

[배울 점]

- 하나의 풀이방식을 고집하지 않기

- 다이나믹 프로그래밍 -> 중복(반복)이 발견되는 작은 문제를 발견하고 이를 기반으로 큰 문제를 풀어나가는 개념 기억하기