[백준 15486번] 퇴사2- java

문제 설명

1. 전체 기간, (한 상담당 필요시간, 받는 돈)이 주어진다.

2. 모든 상담을 합쳐도 전체 기간을 넘어서는 안된다.

3. 상담을 통해 벌 수 있는 최대 금액을 return하면 된다.

 

풀이 과정

 1. DP를 통해 구현 가능하다.

 2. 전체 기간에 대해 날짜별로 구할 수 있는 최대 금액을 모두 구한다.

 3. 예를들어 1일째에는 10원, 2일째에는 25월, 3일째에는 40원....이런 식으로 구해서 날짜별로 구해, 최대 금액이 ans이 될 것이다.

 4. 최대 기간을 넘지 않는 선에서 과거 시간 + 해당 상담으로 벌 돈을 구하면 값이 나올 것이다.

 ex ) 10일 - (3, 10) (5, 20) (1, 10) (1, 20) (2, 15) (4, 40) (2 200)인 경우

1일 (3, 10) -> 4일째에 10원을 번다                          --> 10원이 최대값

2일 (5, 20) -> 6일째에 20원을 번다                          --> 20원이 최대값

3일 (1, 10) -> 4일째에 10원을 번다                          --> 20원이 최대값

4일 (1, 20) -> 5일째에 (10+20) -> 30원을 번다           --> 30원이 최대값

5일 (2, 15) -> 7일째에 (10+20+15) -> 45원을 번다      --> 45원이 최대값

6일 (4, 40) -> 7일을 넘어서서 계산할 수 없다.

7일 (2 200) -> 7일을 넘어서서 계산할 수 없다.

 

 5. 전체 값들 중 필요한 것들만들 더해가며 구하면 될 것이다.

코드