BOJ 2515 - 전시장
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 3429 | 1079 | 754 | 31.814% |
문제
전시장에서 그림을 판매하는 업체에 하나의 전시대가 배정된다. 전시될 그림은 직사각형의 모양을 가지고 있고, 그림의 높이는 다를 수 있지만 폭은 모두 동일하다고 가정한다. 각 그림에는 가격이 매겨져 있다.
업체는 그림들을 관람객에게 보이기 위해 전시대에 배치하는데, 전시대의 폭이 그림의 폭과 동일하여 겹쳐서 배치해야만 한다. 예를 들어, 위의 그림은 전시대에 네 개의 그림 A, B, C, D를 C, B, A, D의 순서로 겹쳐서 배치한 상황을 보여준다.
위 그림의 오른쪽 부분은 전시된 그림들의 배치를 옆에서 본 모양을 나타내고, 왼쪽 부분은 배치한 그림들을 앞에서 보아서 관람객들이 보게 될 모양을 나타낸다. 그림 A는 앞의 그림 B때문에 가려져서 관람객에게 전혀 보이지 않고, 부분적으로라도 보이는 그림은 B, C, D 뿐이다.
보이는 부분의 세로 길이가 특정 정수 S이상인 그림만 관람객이 관심을 보이고 사게 된다고 가정한다. 전시된 그림들 중 보이는 부분의 세로 길이가 S이상인 그림을 판매가능 그림이라고 부른다.
그림의 높이와 가격이 주어질 때, 판매가능 그림들의 가격의 합이 최대가 되도록 그림을 배치할 때, 그 최대합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 그림의 개수 N (1<=N<=300,000)과 판매가능 그림을 정의하는 1이상의 정수 S가 빈칸을 사이에 두고 주어진다. 다음 이어지는 N개의 줄 각각에는 한 그림의 높이와 가격을 나타내는 정수 H와 C가 빈칸을 사이에 두고 주어진다. 단, 1 ≤ S ≤ H ≤ 20,000,000, 1 ≤ C ≤ 1,000이다.
출력
첫째 줄에 판매가능 그림들의 가격의 합이 최대가 되도록 배치했을 때 그 최대 합을 출력한다.
접근
이분탐색을 얹은 간단한 DP 문제이다.
테이블은 이번 높이 - S + 이번 가격, i - 1 번째 table 값중 최댓값을 고르면 된다.
풀이
높이순으로 그림들을 정렬해줬다.
그리고, 순회할 때마다 upper_bound로 height[i] - S의 인덱스를 찾아주었다.
점화식을 코드로 넣어주면 끝난다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int N, S, dp[300001];
pair<int, int> arr[300001];
vector<int> height, price;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
arr[0] = { 0, 0 };
MS(dp, 0);
CIN2(N, S);
FUP(i, 1, N) CIN2(arr[i].first, arr[i].second);
sort(arr, arr + N + 1);
FUP(i, 0, N)
{
height.push_back(arr[i].first);
price.push_back(arr[i].second);
}
FUP(i, 1, N)
{
if (height[i] < S) continue;
int idx = upper_bound(ALL(height), height[i] - S) - height.begin() - 1;
dp[i] = max(dp[i - 1], dp[idx] + price[i]);
}
COUT(dp[N]);
return 0;
}
Author And Source
이 문제에 관하여(BOJ 2515 - 전시장), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gyuho/BOJ-2515-전시장저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)