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

해결방법

DP 알못이 봐도 느껴지는 DP의 향기.. DP를 풀이 안보고 푼건 또 처음이다
dp[i][j] : i일부터 j일까지 상담했을 때 받을 수 있는 금액의 최댓값

DP 테이블 초기화

입력을 받으면서 동시에 dp 테이블을 초기화 해준다. (나는 0일부터 시작해서 N-1일까지로 바꾸어 풀었다.)
dp[상담시작날짜][상담끝난날짜] = 상담금액

ex. dp[0][2] = 10
0일~0일 : 돈 받을 수 없음 -> 0
0일~1일 : 돈 받을 수 없음 -> 0
0일~2일 : 0일에 상담을 진행하면 2일에 끝남 -> 10

이런 식으로 초기화 하면, 테스트케이스 1번의 dp 초기화 결과는 다음과 같다.

DP 테이블 갱신

dp[i][j]는 i번째 상담부터 j번째 상담까지 진행했을 때 받을 수 있는 금액의 최댓값 이므로,
우리가 구하고자 하는 값은 상담의 처음부터 마지막까지 진행했을 때의 최댓값이므로,
해당 문제의 정답은 dp[0][N-1]에 존재하게 된다.

따라서 dp 테이블 갱신은 마지막 상담부터 시작하며, 다음과 같이 진행한다.
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j])

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int dp[16][16];

void solve(){
	for(int i = N-1; i>=0; i--){
		for(int j = i+1; j<N; j++ ){
			for(int k = i; k<j; k++){
				dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin>>N;
	for(int i = 0; i<N; i++){
		int t,p; cin>>t>>p;
        //dp초기화
		dp[i][i+t-1] = p;
	}
	solve();
	cout<<dp[0][N-1];
}

제출결과

dp 연습좀 해야하는데..🙄