#14501 퇴사

# 문제

# 입력 및 출력

# 풀이

어떻게 풀까 고민하다가 2차원 배열을 생각했다

스케줄 배열을 하나 만들어서 1일부터 N일까지 각각의 상담을 진행하고 상담을 완료한 날 받는 비용을 저장하도록 했다

예제 입력 1번을 예로 들면 아래 사진처럼 sch 배열에 금액이 저장된다

1일에 예약된 상담은 3일 째에 상담을 완료하고 비용을 받아 배열의 [1][3] 인덱스에 상담 금액인 10이 저장됨

6, 7일에 예약된 상담은 퇴사일을 넘어가기 때문에 비용을 받지 못해 sch 배열에 저장되지 못함

예제 입력 1에서의 sch 배열

처음에 풀었던 방식이 아래 코든데 내가 다시 봐도 뭔가 이상하다

#include <iostream>
#include <algorithm>
using namespace std;
int T[16], P[16], dp[16], sch[16][16];

int main() {
	int N, maxv = 0;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> T[i] >> P[i];
		if (i + T[i] - 1 > N) continue;
		sch[i][i + T[i] - 1] = P[i];
	}
	for (int i = 1; i <= N; i++) {
		maxv = 0;
		for (int j = 1; j <= N; j++) {
			if (i - T[j] < 0) continue;
			maxv = max(maxv, dp[i - T[j]] + sch[j][i]);
		}
		dp[i] = max(maxv, dp[i - 1]);
	}
	cout << dp[N] << "\n";
}

정답은 됐지만 뭔가 이상하고 코드가 복잡한 것 같아서 다시 풀어봤다

 

https://codejin.tistory.com/173

백준 14501번 C++ 풀이

여기 블로그 참고

 

#include <iostream>
#include <algorithm>
using namespace std;
int T[17], P[17], dp[17];

int main() {
	int N, maxv = 0;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> T[i] >> P[i];
	}
	for (int i = 1; i <= N+1; i++) {
		maxv = max(dp[i], maxv);
		if (i + T[i] <= N + 1) dp[i + T[i]] = max(dp[i + T[i]], maxv + P[i]);
		dp[i] = max(dp[i], dp[i - 1]);
	}
	cout << dp[N + 1] << "\n";
}

상담 기간이 퇴사일을 넘어가지 않는다면 상담 완료 후 받는 비용의 최댓값을 dp배열에 저장

맨 마지막날까지의 최대 비용을 구하기 위해 도중에 상담 없이 넘어가는 경우가 생길수도 있는데

이런 경우엔 계산에 문제가 생길수도 있기 때문에 maxv값을 만들어서 계산해줌

 

뭔가 알듯말듯하다ㅋㅋ

기출문제인것 같은데 이런 유형으로 많이 풀어봐야 익숙해질 것 같다