[백준] 퇴사 - 14501(실버 3)

⚙️ 알고리즘 분류 : DP

🔠 언어 : c++

🤫 힌트.

dp 보고 겁 먹지 말자! index랑 dp에 뭘 넣을지 고민하자.

✏️ 풀이.

문제 풀이 단계
1) dp의 기초는 배열의 차원을 정하고, 각 차원과 dp의 값에 무엇을 넣을지 정하는 것이다.
➡️ 고려해야 할 요소가 N(며칠) 뿐이고, dp에 넣을 값은 이 문제에서 묻는 것이므로 최대 수익을 저장한다.
➡️ dp[N]=(N일째 가질 수 있는 최대 수익)

2) i가 dp 값을 구할 일차다.
j는 i 이하인 수로, i에 영향을 줄 수 있는 경우를 구해서 max 값을 정한다.

⚠️ 헤맨 부분.

• dp[i]=dp[i<=j]
  ➡️ 1일차 dp를 계산하기 위해서, 1일차 뒤에 있는 값들을 이용했다. 하지만 이렇게 하니까 (N일차의 T가 1인 경우, 1일차 다음으로 이동하는 경우)에서 헤맸다.
  그래서 풀이를 보니까, dp[i]=dp[i<=j]가 아니라 dp[i]=dp[j<=i] 형태로 풀면 문제를 해결할 수 있었다.

👩🏻‍💻 코드.

#include <iostream>
#include <vector>
#define mp make_pair
using namespace std;
vector<pair<int, int> > v;
int dp[20];

int main(){
  int n,t,p, answer=0;
  // 입력
  cin>>n;
  for(int i=0; i<n; i++){
    cin>>t>>p;
    v.push_back(mp(t,p));
  }

  // 알고리즘
  for(int i=1; i<=n; i++){
    for(int j=0; j<i; j++){
      t=v[j].first, p=v[j].second;
      if(j+t<=i) dp[i]=max(dp[i], dp[j]+p);
      answer=max(answer, dp[i]);
    }
  }

  cout<<answer;
}

😎 후기.

현타왔다. 실버 3 dp문제인데, 푸는 데 꽤나 고민했다... 실버도 못푸는구나...
dp만 나오면 너무 긴장된다. 답을 보면서 풀이하면 '찬찬히 하면 되네' 싶은 생각이 든다. 내가 풀 수 있는 문젠데, 너무 고민하고 겁먹는 건 아닐까?