BOJ 2515 전시장(Java)
문제 탐색하기
전시장에서 그림을 판매하는 업체에 하나의 전시대가 배정된다.
전시될 그림은 직사각형의 모양을 가지고 있고, 그림의 높이는 다를 수 있지만 폭은 모두 동일하며 각 그림에는 가격이 매겨져 있다.
{: width=”400px”}
그림들을 관람객에게 보이기 위해 전시대에 배치하는데, 전시대의 폭이 그림의 폭과 동일하여 겹쳐서 배치해야만 한다.
위 그림의 오른쪽 부분은 전시된 그림들의 배치를 옆에서 본 모양을 나타내고, 왼쪽 부분은 배치한 그림들을 앞에서 보아서 관람객들이 보게 될 모양을 나타낸다. 그림 A는 앞의 그림 B때문에 가려져서 관람객에게 전혀 보이지 않고, 부분적으로라도 보이는 그림은 B, C, D 뿐이다.
보이는 부분의 세로 길이가 특정 정수 S이상인 그림만 관람객이 관심을 보이고 사게 된다고 가정한다. 전시된 그림들 중 보이는 부분의 세로 길이가 S이상인 그림을 판매가능 그림이라고 부른다.
그림의 높이와 가격이 주어질 때, 판매가능 그림들의 가격의 합이 최대가 되도록 그림을 배치할 때, 그 최대합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 그림의 개수 N과 판매가능 그림을 정의하는 1이상의 정수 S가 빈칸을 사이에 두고 주어진다.
다음 이어지는 N개의 줄 각각에는 한 그림의 높이와 가격을 나타내는 정수 H와 C가 빈칸을 사이에 두고 주어진다.
- 1 ≤ N ≤ 300,000
- 1 ≤ S ≤ H ≤ 20,000,000
- 1 ≤ C ≤ 1,000
출력
첫째 줄에 판매가능 그림들의 가격의 합의 최대값을 출력한다.
예제 입력
6 4
15 80
8 230
10 100
17 200
20 75
26 80
예제 출력
510
코드 설계하기
구현 방법
- 그림 정보 입력 및 정렬:
- N개의 그림 정보를
Painting객체로 저장하고, 높이(H)를 기준으로 오름차순 정렬 ArrayList와Collections.sort()를 이용하여 정렬
- N개의 그림 정보를
- DP 배열 정의:
dp배열을long타입, 크기 N으로 선언dp[i]: 높이 순으로 정렬된 그림 중, 0번부터i번까지의 그림만을 고려했을 때 얻을 수 있는 최대 가격 합
- DP 초기값 설정:
dp[0]은 첫 번째 그림의 가격(paintings.get(0).C)으로 초기화
- 첫 번째 그림만 있을 때는 그 그림을 선택하는 것이 항상 최선
- DP 점화식 계산 (i = 1부터 N-1까지):
- 각
i번째 그림에 대해 다음 두 가지 경우를 고려하여dp[i]를 계산i번째 그림을 선택하지 않는 경우:- 최대 가격 합은 이전
i-1번째까지 고려했을 때의 최대 합과 같다. (=dp[i-1])
- 최대 가격 합은 이전
i번째 그림(높이H_i, 가격C_i)을 선택하는 경우:- 해당 그림이 판매 가능하려면(
S이상 노출), 이 그림 아래에 쌓을 수 있는 그림들의 최대 높이는H_i - S이다.- 이진 탐색을 이용하여
0번부터i-1번까지의 그림 중 높이가H_i - S이하인 그림 중 가장 인덱스가 큰(가장 높이가 높은) 그림j를 찾는다. (binarySearch함수) - 만약 해당
j를 찾았다면(j != -1),i번째 그림을 선택했을 때의 최대 가격 합은dp[j] + C_i가 된다. - 만약 해당
j가 없다면(j == -1),i번째 그림만 단독으로 놓는 경우이므로 이전 합은 0이고, 이때 가격 합은C_i가 된다. (prevDpValue = 0)
- 이진 탐색을 이용하여
- 해당 그림이 판매 가능하려면(
dp[i]는 위 두 경우 중 더 큰 값으로 결정된다. (dp[i] = Math.max(dp[i-1], (j == -1 ? 0 : dp[j]) + paintings.get(i).C))
- 각
- 최종 결과:
dp[N-1]이 최종적인 최대 가격 합이다.
시간 복잡도
- 그림 정보 입력: N개의 그림 정보를 읽고 저장하는 데
O(N)시간이 걸린다. - 그림 정렬:
Collections.sort()를 사용하여 그림들을 높이 기준으로 정렬하는 데O(N log N)시간이 걸린다. - DP 계산:
for루프는 N-1번 반복된다. (O(N))- 루프 내부에서
binarySearch함수를 호출하여j를 찾는 데O(log N)시간이 걸린다. - DP 값을 계산하는 나머지 연산은
O(1)이다. - 따라서 전체 DP 계산 과정의 시간 복잡도는
O(N log N)이다.
- 총 시간 복잡도: 위 단계들을 종합하면, 가장 오래 걸리는 부분은 정렬과 DP 계산이므로 전체 시간 복잡도는 O(N log N) 이다. N이 최대 300,000이므로 충분히 시간 내에 문제를 해결할 수 있다.
정답 코드 (Java)
import java.util.*;
import java.io.*;
public class b2515 {
private static int N, S;
private static ArrayList<Painting> paintings = new ArrayList<>();
private static long[] dp;
// 높이 순으로 정렬된 그림들 중, i+1개 (인덱스 0부터 i까지)만을 고려했을 때 얻을 수 있는 최대 가격의 합
static class Painting implements Comparable<Painting> {
int H, C;
public Painting(int H, int C) {
this.H = H;
this.C = C;
}
@Override
public int compareTo(Painting o) {
return this.H - o.H;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
dp = new long[N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int H = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
paintings.add(new Painting(H, C));
}
Collections.sort(paintings);
// base case 처리
dp[0] = paintings.get(0).C;
// DP 점화식
for (int i = 1; i < N; i++) {
int j = binarySearch(i);
long val = (j == -1) ? 0 : dp[j];
dp[i] = Math.max(dp[i - 1], val + paintings.get(i).C);
}
System.out.println(dp[N - 1]);
}
// paintings[i].H - S 이하의 높이를 가진 그림 중 가장 큰 인덱스를 반환하고
// 없으면 -1 반환
private static int binarySearch(int i) {
int start = 0, end = i - 1;
int target = paintings.get(i).H - S;
int res = -1;
while (start <= end) {
int mid = (start + end) / 2;
int h = paintings.get(mid).H;
if (h <= target) {
res = mid; // 가능한 후보 값 발견
start = mid + 1; // 더 높은 인덱스 가능한지 확인
}else {
end = mid - 1;
}
}
return res;
}
}
Leave a comment