문제 이해 단계
https://www.acmicpc.net/problem/15486
날짜 N과 각 날마다 할 수 있는 일
Ti와 그 일을 했을 때 버는 돈 Pi가 각각 주어진다.
Ti는 그 일을 할 때마다 드는 날을 뜻하며, 그 일을 하는 동안에는 다른 일을 할 수 없다.
이런 상황일 때 돈을 최대한 벌었을 때의 수익을 구하는 문제이다.
문제 접근 단계
이해부터가 살짝 복잡했는데,
N일까지 일을 해서 벌 수 있는 최대수익을 D [N]이라고 하자.
이때 유의해야 할 점은 N일까지라는 것은 N일을 포함하지 않는다.
즉 1~N-1일에 한 일만 포함하는 것이다.
이를 이용해서 1일부터 살펴보자면,
1일까지 일을 해서 번 돈은 당연히 0원일 것이고(D [1] = 0)
1일 때 일해서 번 돈은 3일이 지난 4일째의 받을 수 있다.
일단 이를 D [4] = 10이라도 해두자.
2일까지 일해서 벌 수 있는 최대 수익도 0원이다.(D [2] = 0)
그리고 2일에 일한 돈은 5일 뒤인 7일에 받을 수 있다(D [7] = 20)
이렇게 계속해서 가다가 4일째를 살펴보자.
4일째 받을 수 있는 돈은 크게 2가지가 있다.
1. 1일째에 일한 돈 10원
2. 3일째 일한 돈 10원
만약 이 둘 중 더 큰 게 있다면 그걸 택하면 될 것이다.
D [4] = Max(1일째 번돈, 3일째 번돈)
이런 식으로 N 전일까지 번 돈 D [N]을 구할 때, i번째 일을 할 경우를 비교해 본다.
1. 기존에 N일까지 일해서 벌 수 있는 돈의 총합
2. i일까지 벌 수 있는 돈의 총합 + i일에 일을 했을 때 벌 수 있는 돈
두 경우의 수 중 더 큰 값이 D [N]이 된다.
해당 문제는 말로 설명하는 것이 좀 복잡하기 때문에
코드를 보면서 설명하겠다.
문제 구현 단계
#include <iostream>
#include <utility>
using namespace std;
int N;
pair<int ,int> v[1500010];
int d[1500010];
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin >> N;
for (int i = 1; i <= N; i++)
{
int v1, v2;
cin >> v1;
cin >> v2;
v[i] = make_pair(v1, v2);
}
int cntMax = 0;
for (int i = 1; i <= N+1; i++)
{
cntMax = max(cntMax, d[i]);
if(i+v[i].first > N+1) continue;
d[i + v[i].first] = max(cntMax + v[i].second,d[i + v[i].first]);
}
cout << cntMax;
}입력이 걸리는 일수와 얻는 돈
이렇게 두 가지 정보로 들어오기 때문에 pair을 이용하여 값을 받았다.
그리고 cntMax라는 값을 활용하여, 나온 값들 중 가장 큰 값을 저장한다.
1부터 N+1까지 순차적으로 돌면서 탐색을 한다.
다음 일 까지는 (현재 순서 + 걸리는 일 수) 이기 때문에
i + v [i]. first를 인자로 활용하고, 이 값이 N+1이 넘어가는 것을 방지한다.
그리고 위에 설명했듯이, d [N]은 N전일까지 일했을 때의 최대 돈의 총합이다.
d [i + v [i]. first]는 d [N]를 뜻한다.
max(cntMax + v [i]. second, d [i + v [i]. first]는
(현재 일수까지 일했을 때의 최댓값+현재일 수에서의 일값), (기존)을 의미한다.
그 두 값을 비교하여 더 큰 값으로 d [N]을 갱신한다.
이 과정을 반복하여 cntMax를 계속 갱신한다.
이 과정을 반복하여 cntMax를 출력한다.
시행착오
처음에는 DP를 활용하여 이중반복문을 활용하여 완전탐색으로 풀었다.
그런데 시간초과를 맛보고 여러 가지 방법을 생각해 봤는데 도저히 떠오르지 않았다.
그래서 구글링 해서 이 방법을 알았는데,
풀이를 여러 번 비교해 보고 구현해 보니까 이해가 되더라.
이해하는데 좀 오래 걸렸다.
이 방법은 혼자 생각하기 어려웠던 것 같다.
이런 식으로 DP를 구성하는 방식을 했던 적은 없었던 것 같다.
항상 기준에 되는 인덱스의 배열을 정하는 것만 해봤지,
그 인덱스를 통해 다른 배열의 DP를 정하는 행위는 해본 적이 없어서 이런 방식은 정말 새로웠다.
이해하는 것도 오래 걸렸다.
그래도 한번 해봤으니까 언뜻언뜻 떠올라서 앞으로는 이보다는 더 쉬울 것 같다.