퇴사

- boj 14501 (www.acmicpc.net/problem/14501)

솔루션은 i번째에서부터 마지막날까지 최대 수익을 구하는 것

결국 dp[0] 의 결과가 최댓값이 된다

이때 경우의수는 선택하는 경우와 선택하지 않는 경우 두가지 경우로 나뉠수있는데

선택하는 경우는

pay[i] + dp[day + i]

선택하지 않는 경우는

pay[i + 1] //다음날부터의 최댓값

이 된다

이녀석들중 max 값을 dp[i] 에 세팅해주면 되는 문제이다..

핵심은 뒤에서부터 생각하기!!!

이 문제는 백준이가 최대한 돈을 많이 버는 문제다!!!

첫번째날부터 생각하게 된다면 일을 하는 경우, 안하는 경우로 나뉘게 되는데
그다음 둘째날에는 첫째날의 하는경우에서 둘째날 일을 하는 경우와 안하는 경우
첫째날의 안하는 경우에서 둘째날 일을 하는 경우와 안하는 경우
이런식으로 가지치기가 많이 일어나기 때문에 -> 걍 뒤에서 하세요!!!!

dp = i번째 날부터 마지막 날까지 최대 이득!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

일곱째날

일	1	2	3	4	5	6	7	X
시간	3	5	1	1	2	4	2	X
돈	10	20	10	20	15	40	200	X
일 했을때							0(못함)	X
일 안했을때							0(다음꺼 dp)	X
dp							0	0 <-요거

무려 200원이나 주길래 일을 하고싶지만 7 + 2 = 9로 퇴사 날짜(7)을 지나기 때문에 일을 못합니다..

그래서 dp[7] 은 0입니다

여섯째날

일	1	2	3	4	5	6	7	X
시간	3	5	1	1	2	4	2	X
돈	10	20	10	20	15	40	200	X
일 했을때						퇴사를 해서 못함 (0)		X
일 안했을때						0(다음꺼 dp)		X
dp						0	0	0

40원이나 줘서 조금 일을 하고싶지만 6 + 4 = 10 이여서 일을 못합니다

0원입니다 dp[7]도 0 ㅠㅠㅠㅠㅠ

다섯째날

일	1	2	3	4	5	6	7	X
시간	3	5	1	1	2	4	2	X
돈	10	20	10	20	15	40	200	X
일 했을때					15			X
일 안했을때					0			X
dp					15	0	0	0

5 + 2 는 7이니까 일을 할수있습니다

그때 경우는 dp[7] + 돈[5] = 0 + 15 로 15입니다

일안했을때는 dp[5 + 1] = 0입니다

최댓값은 당근빠따 15죠??ㅇㅈ??

넷째날

일	1	2	3	4	5	6	7	X
시간	3	5	1	1	2	4	2	X
돈	10	20	10	20	15	40	200	X
일 했을때				15 + 20				X
일 안했을때				15				X
dp				35	15	0	0	0

넷째날에 일할수있는지 여부를 확인해보겠씁니다....

4 + 1 = 5여서 일할수있구요

이때 벌수있는 돈은 dp[5] + 돈[4] = 15 + 20 = 35 입니다

일 안했을때는 15에요 (dp[4])

얘들중 최댓값은 일했을떄니까 35겠쬬???

 

셋째날

일	1	2	3	4	5	6	7	X
시간	3	5	1	1	2	4	2	X
돈	10	20	10	20	15	40	200	X
일 했을때			10 + 35					X
일 안했을때			35					X
dp			45	35	15	0	0	0

일할수있는지 여부 확인  3 + 1 =4 썁가능

일했을때 버는 돈 => 돈[3] + dp[4] = 10 + 35

일안했을때 버는 돈 = dp[4] = 35 

dp = 45

 

둘째날

일	1	2	3	4	5	6	7	X
시간	3	5	1	1	2	4	2	X
돈	10	20	10	20	15	40	200	X
일 했을때		20 + 0						X
일 안했을때		45						X
dp		45	45	35	15	0	0	0

일여부 2 + 5 가능

일벌돈: 돈[2] + dp[7] = 20 + 0

일안벌돈: dp[3] = 45

고로 45

 

첫째날

일	1	2	3	4	5	6	7	X
시간	3	5	1	1	2	4	2	X
돈	10	20	10	20	15	40	200	X
일 했을때	10 + 35							X
일 안했을때	45							X
dp	45	45	45	35	15	0	0	0

일할수있는지 여부 확인 1+ 3 = 4 이므로 가능합니다

일했을때 버는 돈 : 돈[1] + dp[4] = 10 + 35

일안했을떄 버는돈 : dp[2] = 45

고로 45입니다!!

 

정답은 45

 

여러분이 할일은

이걸 코드로 구현하는거에요

저는 불친절해서 코드까지 써주지 않습니다!!! 화이팅