14501번. 퇴사 (DP)

http://boj.kr/14501 

 

 

페이의 최댓값을 구하려면 각각의 모든 날짜에 대해서 선택을 하거나 / 하지 않거나 모든 경우를 고려해 봐야 한다.

 

 

점화식

d[n] = max(d[n+1], d[n+T[n]] + P[n])

=

N~n일까지의 최대 페이 = max(N~n+1일까지의 최대 페이, N~n+T[n]까지의 최대 페이+n일의 페이)

=

N~n일까지의 최대 페이 = max(n일에 일을 하지 않았을 때, n일에 일을 했을 때)

 

즉 d[i]가 0일부터 i일까지의 페이가 아니라 i일부터 N일까지의 페이라고 생각해야 한다.

N~i일의 페이라고 생각하면 편하다. 미래에서 돌아온다고 생각.

 

다시한번 점화식의 의미를 하나하나 살펴보면 다음과 같다.

N : 문제에서 주어진 퇴사 전날

d[n] : N일부터 n일까지의 최대 페이 (n이 1이면 문제의 답이 된다)

d[n+1] : n일에 일을 하지 않았을 때의 페이. n일에 일을 하지 않았으므로 N일~n일의 페이 = N일~n+1일의 페이

d[n+T[n]] : N일~n+T[n]일까지의 페이. 

T[n] : n일에 있는 상담에 걸리는 시간

 

예를 들어 문제에서 주어진 대로 이렇게 표가 있다고 했을 때 (N=7)

답을 구하려면

d[1] = max(d[2], d[1+T[1]] + P[1]) = max(d[2], d[4] + 10) 이 된다.

 

7일~1일까지의 최대 페이를 구하려면

7일~2일까지의 페이 + 1일에는 쉼

7일~4일까지의 페이 + 1일에 맡은 상담을 함(10원을 받음)

둘 중에 큰 것을 선택해야 하기 때문이다.

 

 

 

+ 추가 설명

d[n] = max(d[n+1], d[n+T[n]] + P[n])

n일에 일을 하지 않은 게 d[n+1]이라는 건 이해하기 쉬운데,

일을 한 것이 d[n+T[n]] + P[n] 이라는 게 이해가 잘 되지 않았다. 일단 괄호가 많아서 눈에 잘 들어오지도 않는다.

풀어서 말하면 d[n + 상담일수] + n일의 상담 페이 라는 뜻이다. 

 

점화식 우변 max()에 안에 있는 두 값을 그림으로 다시 보자. 이번엔 n 대신 a를 써 보자.

 

d[a+1] = a일에 일을 하지 않았을 때 a~N일의 최대 상담 페이

이게 a일에 일을 하지 않았을 때를 의미하는 d[a+1]다.

빨간색은 그 사이에 벌어들인 돈이다. a일에 일을 하지 않았으므로 0원+d[a+1]이다.

 

 

P[a] + d[a+T[a]] = 일에 일을 했을 때의 최대 상담 페이

이건 d[a+T[a]] + P[a] 이다. 그림 순서대로 보면 P[a] + d[a + T[a]] 이다.

마찬가지로 빨간 글씨는 페이, 그 사이 벌어들인 돈이다. 

뒤에 있는 파란 네모는 d[a + T[a]] 인데,

아직 모르므로 재귀를 호출해서 알아낼 수 있을 때까지 간 다음, 다시 d[1]로 돌아오면 답을 알아낼 수 있다.

(알아낼 수 있을 때까지=d[N]이다)