[백준] 2515번 : 전시장 - 자바(Java)

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

2515번: 전시장

 

문제 해석

 

그림에는 가격이 매겨져 있으며 폭은 모두 동일하지만 높이는 다를 수 있습니다.

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

 

왼쪽 그림은 C, B, A, D의 순서로 겹쳐서 배치한 상황을 보여줍니다.

오른쪽 그림은 전시된 그림들의 배치를 옆에서 본 모양입니다. 

관람객은 보이는 부분의 세로 길이가 특정 정수 S이상인 그림만 구매합니다.

 

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

 

그림의 개수 N과 판매가능한 그림을 정의하는 S가 주어집니다.

 

문제 풀이 전 설계

그림의 개수가 1<= N <= 300,000입니다.

완전 탐색은 불가능해 보이며, O(N)의 시간 복잡도로 풀어내야 할 것 같습니다.

 

 

1. 그림의 길이 순으로 정렬을 해볼까?

작은 것이 앞에 오고 큰 것이 뒤에 오도록 정렬을 해볼 경우에는 문제가 발생할 수 있습니다.

만약에 길이의 순서인 A,B,C,D 순으로 정렬을 했을 때 A가 S 보다 작고, B는 S보다 크다고 가정했을 때 B는 원래 판매 가능한 그림일 수 있지만 A에게 어느 정도 가려져서 보이는 부분이 S보다 작을 수도 있습니다.

 

그러면 정렬한뒤에 A를 B뒤로 보내면 문제가 없을까요?

이 문제는 판매하는 그림의 가치합이 최대가 되어야 합니다.

만약 B,C 가 존재할 때 B가 C를 가리지만 C의 보이는 부분이 S보다 크기가 크다면 문제는 없습니다.

하지만 B가 C를 가려서 S보다 작아지는 경우에 문제가 발생할 수 있습니다.

만약 B의 판매 가격이 C보다 높다면 B가 팔리는 것이 좋습니다.

하지만 C의 판매 가격이 더 높다면? C가 팔리는것이 더 좋습니다.

 

우선 S보다 작은 길이들은 모두 판매불가능하니 뒤로 보낼까 생각했지만 1 <= S <= 길이 < 20,000,000를 만족하기 때문에 그럴 필요는 없습니다.

 

문제가 발생하는 경우와 문제가 발생하지 않는 경우를 나누어 보겠습니다.

 

문제가 발생하지 않는 경우!

A가 B를 가려도 A,B가 모두 판매 가능한 경우

이런 경우에는 이 둘을 하나의 묶음으로 봐도 괜찮을 것 같습니다.

 

문제가 발생하는 경우!

A가 B를 가려서 A만 판매 가능해지며 B는 판매가 불가능한데 B의 판매 가치가 더 높은 경우 B가 앞으로 오는 것이 더 이득입니다.

즉, 자리를 바꿔야 합니다.

 

 

이것을 조금 활용해보겠습니다

 

o는 길이 순으로 정렬했을 때 보이는 부분이 S보다 큼을 의미합니다.

x는 길이순으로 정렬했을때 보이는부분이 S보다 작음을 의미합니다.

 

첫 번째 그림은 판매가 가능하고 자연스럽게 가치 합의 최대는 3이 됩니다.

 

두 번째 그림 또한 판매가 가능하고 가치 합의 최대는 5(3 + 2)가 됩니다.

 

세 번째 그림은 판매가 불가능하므로 현재가치(3)와 가치합 묶음(5)과 비교하려고 했지만 만약 세 번째 그림이 두 번째 그림 자리로 이동했을 때 가치의 합의 최대는 6이 됩니다.

 

네 번째 그림은 판매가 불가능합니다. 현재가치(6) 값이 2번째 그림 자리의 가치인(3) 보다 더 큽니다. 따라서 네 번째 그림이 두 번째 그림 자리로 이동했을 때 가치의 합은 9가 됩니다.

 

다섯 번째 그림은 판매가 가능해서 가치의 합은 16이 됩니다.

 

판매가 가능한 그림의 위치의 가장 최신 위치를 갱신하며 최신 위치의 판매 가치와 탐색 위치의 판매 가치를 비교하여 가치의 합을 증가시킵니다.

 

반례가 존재할까요?

가치의 합은 11로 보입니다.

하지만 만약 세 번째 그림과 다섯 번째 그림만 보았을 때 둘만 존재했을 때 판매 가능하다면?

가치의 합은 17로 증가하게 됩니다.

 

 

검색을 통해 알아보니 정렬하여 이분 탐색을 이용하여 푸는 DP문제입니다.

DP도 어려운데 이분 탐색까지..

 

우선 정렬을 한 다음 앞에서부터 최댓값을 만드는 그림만 선택한다면 O(N)의 탐색으로 DP 테이블을 채울 수 있습니다.

그림의 개수인 N을 기준으로 잡아 DP [i] = i번째 그림까지 얻을 수 있는 최댓값으로 설정해 줍니다.

 

1. i번째 그림이 선택되지 않는 경우

i번째 그림이 선택되지 않는다면 dp [i]는 dp[i-1] 값과 동일합니다.

 

2. i번째 그림이 선택되는 경우

i번째 그림의 높이를 H라고 하겠습니다.

해당 그림을 선택하기 위해서 그림 앞에 H-S 이하의 그림만 배치되어야 합니다.

i번째 까지 H-S 이하의 높이를 가지는 그림들 중 가장 높은 그림을 limit [i]라 하다며 dp [i]는 다음과 같습니다.

dp[i] = dp [limit [i]] + cost

 

이제 Math.max(i번째 그림이 선택된 경우, i번째 그림이 선택되지 않은 경우) 이렇게 점화식을 세워야 하는데 H-S 이하의 높이를 가지는 그림들 중 가장 높은 그림의 index를 저장하는 limit 배열을 생성해야 합니다.

 

limit 배열 생성 ( limit [i] = i보다 앞에 세울 수 있는 그림 중 키가 가장 큰 그림)

앞에 세울 수 있는 그림 중 가장 키가 큰 그림의 경우에는 반복문 2개를 사용하여 탐색하는 경우가 가장 일반적으로 떠오르지만 그렇게 되면 O(N^2)으로 시간 초과가 예상됩니다.

 

따라 이분 탐색을 이용하여 i보다 앞에 세울 수 있는 그림 중 키가 가장 큰 그림을 찾아야 합니다.

그렇게 되면 O(NlogN)만에 해결할 수 있습니다.

 

이분 탐색 코드

static int bSearch(int curPic) {
		// 0 ~ curPic 범위로 세팅
		int mid = 0, left = 0, right = curPic;
		while (left <= right) {
			mid = (left + right) / 2;
			// curPic과 현재 mid의 높이차를 구함
			int diff = paintingArray[curPic].height - paintingArray[mid].height;
			// 높이차가 S이상이면 오른쪽 방향으로 범위를 줄인다.
			if (diff >= S)
				left = mid + 1;
			// S 미만이면 왼쪽 방향으로 범위를 줄인다.
			else
				right = mid - 1;
		}
		// 조건을 만족하면서 curPic에 제일 가까운 인덱스를 리턴
		return right;
	}

 

메인 로직

		DP[0] = paintingArray[0].cost;
        
		for (int i = 1; i < N; i++) {
			int findMaxHightIndex = bSearch(i);
			if(findMaxHightIndex > -1) {
				//탐색 시
				DP[i] = Math.max(DP[limit[findMaxHightIndex]] + paintingArray[i].cost, DP[i - 1]);
			} else {
				//탐색하지 못하면
				DP[i] = Math.max(DP[i-1], paintingArray[i].cost);
			}
			
		}

		System.out.println(DP[N - 1]);

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_2515_전시장 {

	static class Painting implements Comparable<Painting> {
		int height;
		int cost;

		public Painting(int height, int cost) {
			super();
			this.height = height;
			this.cost = cost;
		}

		@Override
		public int compareTo(Painting o) {
			return this.height - o.height;
		}

		@Override
		public String toString() {
			return "Painting [height=" + height + ", cost=" + cost + "]";
		}

	}

	static Painting[] paintingArray;
	static int[] limit, DP;
	static int N, S;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());

		paintingArray = new Painting[N];
		DP = new int[N];
		limit = new int[N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			paintingArray[i] = new Painting(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}

		Arrays.sort(paintingArray);

		// limit 배열 구해놓기 limit[i] i번째 그림까지 얻을 수 있는 그림의 최대 높이
		/*
		 * 어떤원리로 동작하는지 이해되지 않음 for(int i=1; i<N; i++){
		 * 
		 * for(limit[i]=limit[i-1]; limit[i]<i; limit[i]++){
		 * if(paintingArray[i].height-paintingArray[limit[i]].height < S) break; }
		 * limit[i]--; }
		 */

		DP[0] = paintingArray[0].cost;
		
		for (int i = 1; i < N; i++) {
			int findMaxHightIndex = bSearch(i);
			if(findMaxHightIndex > -1) {
				//탐색 시
				DP[i] = Math.max(DP[findMaxHightIndex] + paintingArray[i].cost, DP[i - 1]);
			} else {
				//탐색하지 못하면
				DP[i] = Math.max(DP[i-1], paintingArray[i].cost);
			}
			
		}

		System.out.println(DP[N - 1]);
		System.out.println(Arrays.toString(DP));

	}

	static int bSearch(int curPic) {
		// 0 ~ curPic 범위로 세팅
		int mid = 0, left = 0, right = curPic;
		while (left <= right) {
			mid = (left + right) / 2;
			// curPic과 현재 mid의 높이차를 구함
			int diff = paintingArray[curPic].height - paintingArray[mid].height;
			// 높이차가 S이상이면 오른쪽 방향으로 범위를 줄인다.
			if (diff >= S)
				left = mid + 1;
			// S 미만이면 왼쪽 방향으로 범위를 줄인다.
			else
				right = mid - 1;
		}
		// 조건을 만족하면서 curPic에 제일 가까운 인덱스를 리턴
		System.out.println(right);
		return right;
	}
}

 

 

출처

https://everenew.tistory.com/189

[백준] No.2515 - 전시장 (C++, DP)

https://cpp-shooter.tistory.com/9

[BOJ] 2515 전시장