백준, boj) 2515. 전시장 ( C / C++)

1. 문제 링크

https://www.acmicpc.net/problem/2515

2515번: 전시장

2. 문제 설명

 

업체는 그림들을 관람객에게 보이기 위해 전시대에 배치하는데, 보이는 부분의 세로 길이가 특정 정수 S이상인 그림만 관람객이 관심을 보이고 사게 된다고 가정한다. 전시된 그림들 중 보이는 부분의 세로 길이가 S이상인 그림을 판매 가능한 그림이라고 부른다.

그림의 높이와 가격이 주어질 때, 판매가능 그림들의 가격의 합이 최대가 되도록 그림을 배치할 때, 그 최대합을 구하는 프로그램을 작성하시오.

 

3. 문제 힌트

DP이기도 하지만, 그리디 한 부분도 들어가는 것 같다.

dp[n]을 n개까지 놓았을 때의 최댓값이라고 가정하자.

그럼 dp[n]은 어떻게 구할 수 있을까?

 

놓아서 n번째에 도달한 경우, 안 놓고 n번째에 도달한 경우 2가지가 있을 것이다.

 

4. 문제풀이

dp를 적용하기 위해서 높이 기준으로 정렬을 해야 한다.

 

그리고 n번째 그림을 놓을 때, 자기 앞에 올 수 있는(길이의 차가 S보다 큰) 그림의 Index번호를 저장해야 한다.

처음에 이게 귀찮아서 배열을 그림의 최대 길이 2000만으로 두고 할까 싶었는데 이건 아닌 거 같아서 하다가 말았다.

 

그래서 dp[n]에 도달할 수 있는 경우는

(3)에서 봤듯이 이전 놓을 수 있는 그림에서  자신까지 오는 경우 vs 놓지않고 그냥 오는경우 2가지로 나뉘게 된다.

항상 최댓값을 갖고 값을 쌓아 올라가기 때문에 위의 2가지만 보면 된다.

 

약간 Greedy가 조금 가미된 것 같다.

 

5. 코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int>> v;
vector<int> lim;	//차이가 s이상인 블록중 최대
vector<int> dp;
int n, s;

int main()
{
	scanf("%d %d", &n, &s);
	v.resize(n + 1);
	lim.resize(n + 1);
	dp.resize(n + 1);

	for (int i = 1; i <= n; ++i)
		scanf("%d %d", &v[i].first, &v[i].second);

	sort(v.begin(), v.end());
	
	for (int i = 1; i <= n; ++i) {
		for (lim[i] = lim[i - 1]; lim[i] < i; ++lim[i]) 
			if (v[i].first - v[lim[i]].first < s)break;
		lim[i]--;
	}

	for (int i = 1; i <= n; ++i) 
		dp[i] = max(dp[i - 1], dp[lim[i]] + v[i].second);
	
	printf("%d", dp[n]);


	return 0;
}

 

6. 결과