[백준 / BOJ] 14501 퇴사

문제

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

14501번: 퇴사

백준이는 오늘부터 N+1일째 되는 날 퇴사를 하기위해 남은 N일동안 최대한 많은 상담을 하려고 한다.

 

상담은 상담을 완료하는데걸리는시간 Ti와 이때 얻을수있는 금액 Pi로 이루어져있다.

 

하나의 상담을 하는중 다른상담은 할수없다. 이때, 백준이가 N일동안 상담을했을때 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

 

소스코드

다이나믹 프로그래밍으로 풀은문제다.

일반적인 완전탐색으로 풀경우, 15!번 반복해서 시간초과가 난다.

 

현재 일을 Ni, dp[Ni] = Ni일 까지의 최댓값 이라고하자.

 

현재 날(N(i))부터 N(i-j), N(i-(j+1)), ... , 1일까지 보며, N(i-j)일에 상담을 했을때, N(i)일에 상담을 할수있다면, dp(i)값과 dp(i-j)값의 최댓값을 가져오는 방식으로 풀었다. (O(N^2)최장증가수열 풀듯이..)

 

현재위치보다 작은 모든 위치를 보기때문에,

시간복잡도는 O(N^2)이 된다.

소스코드

https://github.com/devxb/JJUNalgo/blob/master/14501%20%ED%87%B4%EC%82%AC/main.cpp

devxb/JJUNalgo