[백준 14501] 퇴사

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

14501번: 퇴사

 

n=15라서 dfs와 dp모두 가능하다.

 

1번 접근 dfs

모든 경우의 수에 대해 최대 이익을 구하는 것이다. 

 

//브루트 포스 사용
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int max_sum = -1;
int n;

struct Day
{
  int during, val;
};

vector<Day> tasks;
void bruteforce(int cur_day, int val_sum, int val_cur)
{
  if (cur_day == n + 1)
  {
    max_sum = max(max_sum, val_sum);
    return;
  }
  else if (cur_day > n + 1)
  {
    max_sum = max(max_sum, val_sum - val_cur);
    return;
  }

  for (int i = cur_day + tasks[cur_day].during; i <= n + tasks[cur_day].during; i++)
  {
    bruteforce(i, val_sum + tasks[cur_day].val, tasks[cur_day].val);
  }
}

int main(void)
{
  scanf("%d", &n);
  tasks.push_back({0, 0});
  for (int i = 0; i < n; i++)
  {
    int d, v;
    scanf("%d %d", &d, &v);
    tasks.push_back({d, v});
  }

  for (int i = 1; i < n + 1; i++)
  {
    bruteforce(i, 0, 0);
  }
  printf("%d\n", max_sum);
  return 0;
}

 

 

2번 접근 dp

점화식 세우는 부분에서 많이 헷갈렸다.

dp[i] i번째 날에 받을 수 있는 최대 임금이라고 한다면

현재 시점에서 일을 한다 / 하지 않는다에 대한 점화식은

//오늘 일을 한다면 t[i]일 후 최대 임금

dp[i + t[i] ] = max(dp[i] + p[i], dp[i+t[i])

//오늘 일을 하지 않는다면

dp[i+1] = max(dp[i], dp[i+1])

이 될 것이다.

 

#include <stdio.h>
#include <algorithm>

using namespace std;
int n;
int dp[16];
int arr[16][2];
int main(void)
{
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
  {
    scanf("%d%d", &arr[i][0], &arr[i][1]);
  }
  int result = 0;
  for (int i = 1; i <= n; i++)
  {

    if (i + arr[i][0] <= n + 1)
    {
      dp[i + arr[i][0]] = max(dp[i + arr[i][0]], dp[i] + arr[i][1]);
      result = max(result, dp[i + arr[i][0]]);
    }

    dp[i + 1] = max(dp[i + 1], dp[i]);
    result = max(result, dp[i + 1]);
  }

  printf("%d", result);
  return 0;
}