[C++] 백준 14501 - 퇴사

🔐 백준 14501 - 퇴사

https://www.acmicpc.net/problem/14501

🔑 풀이

N의 범위가 15이하로 작고, 시간 제한이 2초임을 확인하고, 완전탐색으로 풀어도 문제가

없을 것 같다고 먼저 판단했다. 또한 문제를 보고 DP로도 풀 수 있을 것 같아 DP로 풀게

되었다.

DP에서 중요한 부분이 DP 배열을 어떻게 선언할 것인지인데, i 번째 날 가질 수 있는 최대

금액을 배열로 두었다. consult 배열의 first에 상담에 걸리는 시간을, second에 금액을

저장하고, i번째 날에 상담을 할 수 있는 지를 확인하고, 가능하다면 최대값 비교를 통해 값을

갱신해주는 방식으로 문제를 해결하였다.

🧩 코드