[14501] 퇴사, c++

[14501] 퇴사

 

www.acmicpc.net/problem/14501

14501번: 퇴사

한줄 후기 : 내가 dp를 보자마자 풀기 보다 오마이걸 지호 만나서 친해지기가 빠를듯

 

퇴사는 알고스 과제에서 한 번 풀어보려 시도했었다가 어려워서 안 푼 문제다.

정답률이 꽤 높은 편이라 셋이서 도전 ^^

나는 DP 문제랑 정말 안맞는 것 같아.

 

#include <iostream>
#include <algorithm>
using namespace std;
int p[16];
int t[16];
int dp[16];
int main(){
	int n;
	int day;
	cin >> n;
	for(int i=1; i<=n; i++){
		scanf("%d %d", &day, &p[i]);
		t[i] = day+i;
	}
	int temp = 0;
	for(int i=1; i<=n; i++){
		if(t[i] <= n+1)	dp[i] = p[i];
		for(int j=1; j<i; j++){
			if(t[j] <= i){
				temp=max(dp[j], temp);	
			}
		}
		dp[i] += temp;
		temp=0;
	}
	int max1 = 0;
	for(int i=1; i<=n; i++){
		if(max1 < dp[i])	max1 = dp[i];
	}
	cout << max1;
}

처음에 t 배열에 입력 받은 일 수를 그대로 넣으려 했는데 생각해 보니 어차피 현재 일수 + 상담에 걸리는 일수 를 무조건 연산해야 할 것 같아서 그냥 day+(index)를 입력 때 계산해서 t 배열에 넣어줬다.

p 배열에는 상담 수익

사실 여기까진 내가 했지만 거의 지혜가 다 풀었다ㅋㅋ 지혜야 넌 천재야!

우선 t 값이 백준이가 근무할 수 있는 n+1 이하임을 확인하고, 그때 dp 배열에 상담 수익을 넣어준다.

그 후 현재 일수 까지 t 값보다 작은 값이 존재한다면 그때 dp 값과 임시변수 (초기값 = 0) 를 비교하여 더 큰 값을 temp에 대입

마지막으로 그 temp와 dp[i]를 더해준다.

마지막으로는 dp배열의 max 값을 찾아 출력.

결과적으로 dp[n] => n일 까지 얻을 수 있는 수익

​

어렵다 어려워.