[BOJ] 14501번 퇴사 (C++)

문제 링크 (https://www.acmicpc.net/problem/14501)

14501번: 퇴사

dp와 브루트포스로 풀 수 있는 문제 !! 나는 dp로 풀었다. 

n일을 일하며 얻을 수 있는 최대 수익을 구해야 하는데 상담이 가능하다고 해서 바로 진행하는 것이 아니라 그 뒤에 더 좋은 수익이 나는 상담이 있을 수도 있으니 이 점을 체크해야 한다.

나는 2xn 크기의 배열을 사용했는데 0행의 각 열은 그 날까지 얻을 수 있는 최대 수익을, 1행의 각 열은 그날 상담을 시작한다면 며칠이 걸리는지 넣어주었다.

 

1. 해당 날짜에 시작하는 상담이 남은 기간 동안 가능한 상담인지 (ex) N = 7인 경우, 6일에 잡힌 상담이 4일짜리면 불가능)

2. 이전에 시작한 상담들 중 상담 기간이 끝난 (오늘부터 이어서 상담이 가능한) 케이스가 있는지 

   2-1. 있다면? 그 날까지의 최대 수익(배열 0행)을 기억

3. 2-1에서 기억해둔 최대 수익 중 가장 큰 값(max_value)에 해당 날짜에 시작하는 상담의 수익을 더해 배열에 그 값 넣기

4. 배열 0행 중 가장 큰 값 출력

 

[예제 1 배열]

[예제 4 배열]

---

[소스코드]

---

2021-10-07

Silver 3

알고리즘 분류

- 다이나믹 프로그래밍

- 브루트포스 알고리즘