[백준/C++] 15486번. 퇴사 2

문제

15486번: 퇴사 2

---

1. 첫 번째 풀이

사고 과정

이번에도 DP 문제.

 

특정 날에 시작, T일 후 끝나는 상담 진행 시 P원을 받는다. 퇴사까지 N일이 남았을 때, 최대한 돈을 버는 방법을 구하는 문제.

 

이번에도 저번 문제, 점프 점프와 비슷하게 생각하고, 빠르게 코드를 짜 제출했다.

 

간단히 알고리즘을 설명하자면

1. 0일부터 N일까지 크게 반복(i)
2. i일에 상담을 시작하면 i + t[i]일부터 P[i]원을 받을 수 있다.
   1. 그러니 i + t[i]일 부터 N일까지, P[i]원을 기록한다.
3. 만약 이미 써있는 가격 P가, 내가 상담을 진행해 얻을 max[i] + P[i]보다 작다면 값을 변경하지 않는다.
   1. 이때, 여기 써있는 가격은 i일 이전에 상담을 시작해 번 돈이므로, i일로 갱신한다고 손해볼 일은 없다.

 

코드

#include <iostream>
#include <vector>

int main() {
	int n;
	std::cin >> n;
	
	std::vector<int> t(n), p(n), max(n + 1, 0);
	for (int i = 0; i < n; ++i) {
		std::cin >> t[i];
		std::cin >> p[i];
	}

	for (int i = 0; i < n; ++i) {
		for (int j = i + t[i]; j <= n; ++j) {
			if (max[i] + p[i] > max[j]) {
				max[j] = max[i] + p[i];
			}
		}
	}

	std::cout << max[n];
}

 

결과

 

하지만 시간 초과로 실패했다.

---

2. 마지막 풀이

사고 과정

원인을 분석해보니, N의 최댓값이 1,500,000이었다. i + t[i]일 이후로 N일까지 전부 갱신하는 내 코드는 대략 O(N^2)의 시간복잡도를 가질테니, 당연한 결과였다.

 

그럼 모든 값을 갱신하지 말아야 하나? 어떤 값만 갱신해야 효율적일까?

 

그래서 생각한 게, i + t[i]일 하나만 갱신하자!였다. 그리고 동시에, i일에 도착했을 때, i-1일과 현재 값 중 더 큰 값을 고르게 설계했다.

 

이러면 기존 코드처럼, 최적해가 앞쪽에 몰린 경우에도 모든 값이 갱신되며, 상담으로 더 좋은 최적해를 만난다면 이 또한 갱신된다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
	int n;
	std::cin >> n;
	
	std::vector<int> t(n), p(n), max(n + 1, 0);
	for (int i = 0; i < n; ++i) {
		std::cin >> t[i];
		std::cin >> p[i];
	}

	for (int i = 0; i < n; ++i) {
		int j = i + t[i];

		if (j <= n) {
			if (max[i] + p[i] > max[j]) {
				max[j] = max[i] + p[i];
			}
		}

		max[i + 1] = std::max(max[i + 1], max[i]);
	}

	std::cout << max[n];
}

 

j값으로 for문을 돌릴 필요가 없어졌다. 2중 반복문이 1중 반복문이 되었고, 연산 결과는 변하지 않는다.

 

결과

 

이 로직으로 문제를 통과할 수 있었다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/12932909

YunGoon님의 코드. 역시나 알고리즘은 동일하나, 꽤 많은 차이가 있다.

 

내 코드와 비교

내 코드는 0에서 N으로 진행했기에, i일을 기준으로 했을 때

 

1. 상담을 통해 갱신되는 건 i + @의 값
2. 전날과 비교해 갱신되는 건 i

라는 괴리감이 있다. 그래서 코드가 직관적이지 못하다.

 

하지만 이 분은 N에서 0으로 진행했다. 그에 따라

1. 상담으로 갱신되는 건 i의 값(i + t[i]의 값에서 p[i]를 더했다.)
2. 전날과 비교해 갱신되는 것도 i의 값

으로 통일감이 있어, 코드 해석이 한결 수월해졌다.

 

진행 방향을 틀어버림으로써 일관성을 유지시킬 수 있다니. 한 수 배웠다.

---

강평

생각은 잘 떠올렸지만, 이를 말로 풀어내긴 쉽지 않았던 문제. 다른 분의 코드를 보기 전까진, 이게 왜 되는지, 왜 시간이 줄어드는지 명확히 설명할 수 없었다. 역시 다른 코드를 볼 때 성장한다.