[백준] 14501번 퇴사

14501번 퇴사

---

1. 이해하기

• 상담을 하여 가장 많이 받을 수 있는 금액을 얻는 방법.
• 모든 날의 상담을 할 수 있는 것이 아닌 최종 일전까지만 상담을 받을 수 있고 상담이 최종일까지 끝나야 한다.
• 완전탐색과 DP로 풀 수 있다.

---

2. 구현하기

• 완전탐색 방법

  • 최종일을 넘는 경우에는 상담을 하지 못하므로 0을 반환한다.
  • day+1을 넣어주는 경우는 그 날에는 상담을 하지 않고 다음 날에 상담을 하는 경우도 찾아주기 위해서이다.

  int solve(int day, int pay) {
      if(day > N) return 0;
      if(day == N) return pay;
  
      int ret = 0;
      ret = max(ret,solve(day+1,pay));
      ret = max(ret,solve(day+schedule[day].day,pay+schedule[day].pay));
      return ret;
  }

---

3. 전체 코드

• 완전탐색

  #include <iostream>
  #include <cstring>
  using namespace std;
  struct INF{
      int day,pay;
  };
  INF schedule[20];
  int N;
  
  int solve(int day, int pay) {
      if(day > N) return 0;
      if(day == N) return pay;
  
      int ret = 0;
      ret = max(ret,solve(day+1,pay));
      ret = max(ret,solve(day+schedule[day].day,pay+schedule[day].pay));
      return ret;
  }
  
  int main() {
      cin >> N;
      for(int i = 0; i < N; i++) cin >> schedule[i].day >> schedule[i].pay;
      cout << solve(0,0) << '\n';
      return 0;
  }

• DP

  #include <iostream>
  using namespace std;
  struct INF{
      int day,pay;
  };
  int cache[16];
  INF schedule[15];
  int N;
  
  int main() {
      int N;
      cin >> N;
      for(int i = 0; i < N; i++) {
          cin >> schedule[i].day >> schedule[i].pay;
      }
      for(int i = 0; i < N; i++) {
          if(i-1 > 0) cache[i] = max(cache[i],cache[i-1]);
          cache[schedule[i].day+i] = max(cache[schedule[i].day+i], cache[i]+schedule[i].pay);
      }
      int ans = 0;
      for(int i = 0; i <= N; i++) {
          if(cache[i] > ans) ans = cache[i];
      }
      cout << ans << '\n';
      return 0;
  }