문제
접근 방법
처음에 이 문제를 보고 떠올린 아이디어는 :
입력들이 들어올 때, 각 입력값을 배열에 알맞은 기준에 따라 집어 넣습니다.
각 입력 값을 배열 공간에 넣는 규칙은 예시를 들어 설명해 보도록 하겠습니다.
배열의 이름을 greedy 라고 합시다.
입력 값이
7
4 60
4 40
1 20
2 50
3 30
4 10
6 5
라고 한다면,
처음의 입력 값인 4, 60에 대하여 greedy[4]에 60을 집어 넣습니다. 다음 입력 값인 4, 40에 대하여 greedy[4]에 40을 넣으려고 하였지만, 이미 60이라는 값이 있기 때문에 40과 60을 비교합니다. 40이 60보다 작기 때문에, 이번에는 greedy[3]을 확인합니다. greedy[3]에는 아무 값도 들어있지 않는다는 것을 뜻하는 0이 있기 때문에, 여기에 40을 집어 넣습니다.
1, 20에 대하여 greedy[1] = 20, 2, 50에 대하여 greedy[2] = 50 을 대입합니다.
3, 30에 대하여 greedy[3] = 30을 해야 하지만, greedy[3]에는 아까 전에 이미 40을 넣어 두었습니다. 따라서, 30과 40을 비교하고 30이 40보다 작으므로 이번에는 greedy[2]와 현재 입력값을 비교합니다. greedy[2]에는 이미 50이 들어 있고 입력값인 30이 50보다 작으므로 greedy[1]과 30을 비교합니다. greedy[1]의 원래 값인 20보다 30이 더 크므로, greedy[1]을 30으로 갱신하여 줍니다.
즉, 현재 인덱스 1부터 현재 인덱스까지의 배열 공간의 값들 중에 가장 작은 값과 비교를 하여 해당 배열 공간에 입력값을 갱신하여 주는 것입니다.
4, 10에 대하여 greedy[4] 부터 위와 같은 과정으로 greedy[3], greedy[2], greedy[1] 과 입력값인 10을 비교하지만, 모두 10보다 크므로 10은 greedy 의 인덱스 1부터 4까지의 공간 중 갱신될 수 있는 곳이 없어 소멸 됩니다.
마지막으로 6과 5 에 대하여 greedy[6] = 5 를 대입해 줍니다.
여기까지의 과정으로 greedy 배열에는 30, 50, 40, 60, 0, 5 가 들어 있고 이를 모두 합하여 주면 우리가 원하는 결과를 얻을 수 있습니다.
반례
위와 같은 논리가 틀리지 않은 것처럼 보이지만, 반례가 있습니다.
입력
5
3 1
3 2
3 3
2 10
1 10
을 예로 들어서 설명해 보도록 하지요.
입력 3, 1에 대하여 greedy[3] = 1.
입력 3, 2에 대하여 greedy[3] 에는 이미 값이 있으므로 greedy[2] = 2 를 해줍니다.
입력 3, 3에 대하여 greedy[2] 에는 이미 값이 있으므로 greedy[1] = 3 을 해줍니다.
여기까지 배열 공간에는 3, 2, 1 이 들어 있습니다.
입력 2, 10에 대하여 greedy[2]에 이미 2가 들어 있고, 입력값 10이 2보다 크므로 greedy[2] = 10으로 갱신하여 줍니다. 입력 1, 10에 대하여 greedy[1]에 이미 3이 들어 있고, 입력값 10이 3보다 크므로 greedy[1] = 10 으로 갱신하여 줍니다.
즉, 최종적으로 배열 공간에는 10, 10, 1 이 들어가게 되는데, 직관적으로 생각하였을 때 과제 점수의 최댓값은 10, 10, 3 으로 21이 아닌 23이 되어야 합니다.
해결 방법
그렇다면 이러한 반례는 왜 생기는 것일까요?
d = 3 일 때 w 는 각각 1, 2, 3 입니다. 이를 순서대로 입력하면 배열에는 3, 2, 1 이 남습니다. 1, 2, 3 이 되어야만 앞으로 계산할 때 10, 10, 1 이 아닌 10, 10, 3이 되어 최댓값을 만들 수 있을 텐데 말이죠.
이는 값들을 모두 입력 받은 후에, w 에 대하여 내림차순으로 먼저 정렬을 했을 때 해결이 됩니다.
처음의 입력값들을 w의 기준으로 내림차순 정렬을 하면
2 10
1 10
3 3
3 2
3 1
이 됩니다.
정렬 후에 위의 과정을 반복하면, 우리가 원하는 값을 얻을 수 있게 됩니다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int, int>a, pair<int, int>b) {
return a.second > b.second;
}
int main()
{
int N;
cin >> N;
vector<pair<int, int> > v;
int d, w;
for (int i = 0; i < N; i++) {
cin >> d >> w;
v.push_back(pair<int, int>(d, w));
}
sort(v.begin(), v.end(), compare);
// for (int i = 0; i < N; i++) {
// cout << v[i].first << " " << v[i].second << endl;
// }
int greedy[1001] = {0};
int index, limit = 0;
for (int i = 0; i < N; i++) {
d = v[i].first;
w = v[i].second;
index = d;
if (limit <= d) limit = d;
for (int k = d; k >= 0; k--) {
if (greedy[k] == 0) {
index = k; break;
}
if (greedy[index] < greedy[k]) {
index = k;
}
}
if (greedy[index] < w)
greedy[index] = w;
}
int result = 0;
for (int i = 1; i <= limit; i++) {
result += greedy[i];
}
cout << result;
}