백준 14501번 <퇴사> - C++

 

 

 

 

 

 

처절했던 사투에 비해 코드는 간결하구나..

 

문제가 많았다.

1. 점화식 제대로 못 찾음.

2. 문제 자체를 정확하게 이해하지 못했음

3. 내가 짠 코드를 내가 이해하지 못함

 

문제 설명부터 시작해서 차근차근 다시 이해해보자

---

	1일	2일	3일	4일	5일	6일	7일
$T_i$	3	5	1	1	2	4	2
$P_i$	10	20	10	20	15	40	200
$dp[i]$	0	0	0	0	0	0	0

 

1일에 상담을 했다면, 2 3일에는 상담을 할 수 없다. 그러므로 $1+T_i$인 4, 즉 dp[4]에는 1일차 $P_i$인 10이 들어간다

---

	1일	2일	3일	4일	5일	6일	7일
$T_i$	3	5	1	1	2	4	2
$P_i$	10	20	10	20	15	40	200
$dp[i]$	0	0	0	10	0	0	0

 

1일에 하지 않고 2일에 상담을 했다면,

3 4 5 6일에 상담을 할 수 없으므로, 7일에 2일차 $P_i$인 20이 들어간다

---

	1일	2일	3일	4일	5일	6일	7일
$T_i$	3	5	1	1	2	4	2
$P_i$	10	20	10	20	15	40	200
$dp[i]$	0	0	0	10	0	0	20

 

1, 2일을 건너뛰고 3일에 상담을 했다면,

4일에도 바로 상담을 할 수 있고, 10이 들어간다. 그런데 이미 10이 들어가 있으므로, 최댓값을 계산할 땐 의미가 없다. 문제에서 총 얼마를 받는 지가 궁금했던 거지, 언제언제 상담을 할 수 있는 지가 궁금한 것은 아니다.

---

	1일	2일	3일	4일	5일	6일	7일
$T_i$	3	5	1	1	2	4	2
$P_i$	10	20	10	20	15	40	200
$dp[i]$	0	0	0	10	0	0	20

 

암튼 4일까지의 최대로 받는 돈은 10이다. 4일에 상담을 진행한다면, 5일의 dp[i]에 $dp[i]+T_i =10+20=30$이 들어가게 된다

---

	1일	2일	3일	4일	5일	6일	7일
$T_i$	3	5	1	1	2	4	2
$P_i$	10	20	10	20	15	40	200
$dp[i]$	0	0	0	10	30	0	max(20,45)

 

5일에 상담을 받으면, 6일에 받지 못한다.

그렇다면 7일에 받을 수 있는 돈은 15+30=45인데, dp[7]에는 이미 20이 들어가 있다. 여기서 비교를 해야 한다.

dp[i+T[i]] = max(dp[i+T[i]], dp[i]+P[i])

이미 들어가 있는 값과, 새로 만들어진 값 중 더 큰 값을 저장한다!!

---

	1일	2일	3일	4일	5일	6일	7일
$T_i$	3	5	1	1	2	4	2
$P_i$	10	20	10	20	15	40	200
$dp[i]$	0	0	0	10	30	0	45

 

6일과 7일에 상담을 받으면, 퇴사기준일을 넘어가버린다.. 반복에선 포함하는 범위지만, 데드라인을 넘어가서 값을 갱신하

지 않는다.

 

---

 

전체 코드

#include <algorithm>
#include <cmath> //C++
#include <iostream>
#include <math.h> //C
#include <queue>
#include <string>
#include <vector>

int *T;
int *P;
int *dp;

using namespace std;

int main() {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n;
  cin >> n;

  T = new int[n + 7];
  P = new int[n + 7];
  dp = new int[n + 7];

  fill(dp, dp + (n + 7), 0);

  for (int i = 1; i <= n; i++) {
    cin >> T[i] >> P[i];
  }

  int maxi=0;
  //n+1일째에 상담이 끝나도 안 돼
  for (int i = 1; i <= n+1; i++) {
    //cout << "maxi : " << maxi << " " << "dp[i] :" << dp[i] << '\n';
    dp[i] = max(maxi, dp[i]);
    //cout << "maxi now : " << maxi << '\n';
    if (i + T[i] <= n+1) {
      //cout << "오늘 : " << i << " 다음 상담 시작일 : " << i + T[i] << '\n';
      //cout << "비교대상 : " << dp[i+T[i]] << "  " << P[i] + dp[i] << '\n';
      dp[i + T[i]] = max(dp[i + T[i]], P[i] + dp[i]);
      //cout << i+T[i] << "일의 최대 상담금액 : " << dp[i + T[i]] << '\n';
      //이미 들어가 있는 최대랑, 들어갈 최대를 비교 : i일까지의 상담액의 최대
    }
    //if(i==n && T[i]==1){dp[i+1] += P[i];}
    //cout << "갱신 전 maxi : " << maxi << " " << "dp[" << i+T[i] <<"]:" << dp[i+T[i]] << '\n';
    maxi = max(maxi, dp[i]);
    //cout << "갱신 후 maxi : " << maxi << " " << "dp[" << i+T[i] <<"]:" << dp[i+T[i]] << '\n';
  }
  cout << maxi << '\n';
  
  delete[] T;
  delete[] P;
  delete[] dp;
  return 0;
}

 

$i+T[i] <= n+1$인 이유는, 위에서 설명했다 시피 n일에 m일짜리 상담을 잡으면 그 금액이 n+m일에 기록되기 때문이다

 

dp[i] = max(maxi, dp[i]);

이 코드를 작성해야 할 것을 몰라서 몇 시간을 헤맸는데, 무슨뜻이냐?

 

지금 자리에, 지금까지 상담액의 최대를 기록한다는 뜻이다.

= 오늘 기준으로 끝나는 상담이 없다고 dp[i]를 0으로 두는 것이 아니라, 이전까지의 최대를 기록해 둔다는 것이다. 유남쌩

 

Intellectual Honesty