백준#14501

★★★☆☆☆☆☆☆☆

14501번: 퇴사

---

---

문제 접근 방식

처음에 이문제를 봤을 때는 이게 왜 DP문제일까 생각했다.

브루트 포스 알고리즘으로 접근해서 풀어도 시간이 안 부족할 것 같다고 생각이 들었는데

조금 더 생각을 해보니까 1,4,5일 차를 상담하는 게 최댓값이라면 1,4,5일 차까지의 최대 수익이 필요하다고 생각했다.

그렇다는 것은 5일 차까지의 최대 수익은 5일 차에 일할수 있는 모든 경우의 수를 계산하는 것이다.

이 값을 계산하지않는다면 5일 차까지의 값이 계속 필요한 경우 계속해서 이전 절차(5일 차까지의 수익 구하기)를 반복해야 한다. 

즉, 1,2,3,4,5,~N일까지의 최대 수익을 메모이제이션을 해주면 된다는 것을 알았고 아래 예제를 점화식으로 생각해본다면,

최댓값은 45로 1,4,5일을 일하는 것이다. 그러면 딱 7일까지 상담을 하게 된다.

f(7)=f(5)+15, f(5)=f(4)+20, f(4)=f(1)+10으로  표현해볼 수 있다.

f(1)은 0일에서 하루를 일하면 1일째가 되는데 0일은 없으므로 f(1)은 0이고,  1일에는 총 상담기간이 3일이므로 상담이 끝나면 4일이 된다 상담 수당을 더하면 10인 것이다.

즉, 일을 했을 때 n일이 되는 수익과 n일에 일을 했을 때에 수익을 더하는 것이다. 

---

어려웠던 점

페이의 최댓값을 계산할 때 6일 차에 일하고 7일 차에 쉬고 8일 차에 일하는 것처럼 쉬는 날이 있을 때를 고려하는 게 어려웠다.이 부분을 제일 많이 고민했었는데 그래서 나는 dp [1]이 1일 차까지의 수익이라면 1일만 근무하고 모든 날을 쉰다는 것을 나타내기 위해 dp [N+1]까지 dp [1]이 dp [index] 값보다 크다면 모두 할당해주었다. 

이게 무슨 말이냐면 1일 차에 일하고 나머지를 모두 쉰다와 안 쉬고 일을 했을 때 1일 차가 되었다의 수익을 비교하는 것이다.

vector<int>dp(17); //n일까지의 최대수익을저장
//인덱스를 1부터 15+1까지 쓰기위해 17까지 벡터를 초기화함
vector<pair<int, int>>work(17); //상담일과 상담수당을 저장하는 벡터
pair<int, int>p;
int N; 
void schedule(int day) { //bottom_up 1부터
	for (int i=day-1; i > 0; i--) { 
		if (i + work[i].first == day) { //i일+i일에 일할때 상담기간=해당일자?
			dp[day] =max(dp[day], dp[i] + work[i].second); //가능한 모든 수당을 비교
		}
	}
	if (dp[day]) { //dp[pay]값이 0일때를 걸러줌,day일이후에 값을 모두 변경
		for (int i = day + 1; i <= N + 1; i++) {
			dp[i] = max(dp[i], dp[day]);
		}
	}
	if (day <= N)schedule(day + 1);
	else return;
}


int main() {
	cin >> N;
	int ti, pi;
	for (int i = 1; i <= N; i++) {
		cin >> ti >> pi;
		p = make_pair(ti, pi);
		work[i] = p;
	}
	schedule(1);
	cout << dp[N + 1];
}

---

느낀 점

아직까지 DP가 와닿진 않는 것 같다. 변수명을 알맞게 설정하는 것도 생각보다 꽤 어렵다.. 멘토님들의 코드를 보면 딱 보면 와닿는데 더 노력해야겠다.