[알고리즘][8][백준_2515][C언어] - 전시장

 

 

---

문제이해

문제에서는 총 N개의 그림이 주어지고 각 그림마다 높이와 가격이 존재한다.

 

중요한 부분은 앞에서 보았을때 보이는 폭의 길이가 특정정수 S이상이 되어야 판매가능한 그림이 된다는점이다.

 

이부분을 중점으로 생각해보자

 

 

---

알고리즘 전략

먼저 앞에서 봤을때 보이는 폭의 길이가 중요한 포인트이므로 높이와 가격을 가진 각각의 그림들을 구조체로 선언해주고 높이를 오름차순으로 정렬해주자.

 

그리고 배열 dp[i]를 이렇게 정의하자.

 

dp[i] : i번째그림까지중 i번째그림을 무조건 선택한다고 했을때 최대 가격의 합

 

그리고 문제에서는 모든 그림들을 배열한다고 했지만 편의상 총가격에 포함되는 그림들을 선택하고 불필요한 그림들은 선택하지 않는다고 생각하자.

 

그렇다면 점화식은 어떻게되는지 보자.

 

price[i] 를 i번째 그림의 가격이라고 하면

 

dp[i] = max ( price[i] + dp[j] ) (0 <= j < i)

 

가 될것이다. 단 여기서 dp[j] 는 j번째 그림을 무조건 선택했다는 의미이고 price[j]를 더해주었던 값이므로 i번째 그림과 j번째그림의 높이차이가 s이상 된다는 조건을 만족해야한다.

 

이런구조로 알고리즘을 설계하면 아래와같이 이중for문으로

O(N^2) 의 시간복잡도를 가지게되고 n 크기가 최대 30만 이므로 시간초과일것이다.

 

따라서 시간을 더 줄일수 있는 방안을 생각해보아야한다.

for(i=0;i<n;i++){
    for(j=0;j<i;j++){
    	code
    }
}

 

 

여기서 시간을 줄일수 있는 방법은 두번째 for문을 없애는 것이다.

 

다음 예제를 보면서 생각해보자.

 

N=5이고 S=5 이면서

각각의 그림들의 높이와 가격이 다음과 같다고 가정하자.

 

 

여기서 기본적인 위 방식으로는 dp[4]를 구하기위해서 j=0일때부터 j=3일때까지 dp[j]를 모두 순회해야하지만 그러지 않고 마지막 그림과 연관이 있는(4번째 그림보다 앞에있는 그림중 차이가 S이상 안나는 그림들)그림들과 그렇지 않은 그림들로 구분을 해보자.

 

 

 

위 그림에서 회색그림을 기준으로 노란그림들은 회색그림과 길이가 s이상( 5 이상 ) 차이나는 그림들이고 빨간그림은 s미만으로 차이가 나는 그림이다. 이와같이 구분을 하는 이유는 회색그림의 dp인 dp[4] 를 구할때 dp[0] dp[1] dp[2] dp[3] 이 네가지를 전부 고려할 필요없이 노란그림들의 dp값중 최대값에 price[4] 를 더한값이 dp[4]가 된다.

 

그이유는 dp[i]의 정의가 해당그림을 무조건 선택했다는 의미이므로 만약 빨간그림인 dp[3]을 고려하게되면 i=4,5인 그림 모두를 선택하는의미인데 두 그림의 높이차이가 5 미만이므로 둘다 선택할수는 없기에 노란그림들중 최대가격을 만들수 있는 조합을 선택하면 dp[4]를 구할수 있다. 따라서 i 가 증가함에 따라 어디까지가 노란그림들 구역이고 어디부터가 빨간그림 구역인지 알려주는 변수가 하나 필요하고 반복 순회를 피하기 위해 노란그림들중 dp값이 가장 큰 값과 그 인덱스를 저장할 변수 두개가 필요하다.

 

최종적인 코드는 아래와같다.

#include <stdio.h>
#include <stdlib.h>

typedef struct PIC{
    int height;
    int price;
}Pic;

int dp[300001] = {}; // i번째 그림을 맨끝에 세울때 최대 수익
Pic arr[300001];

int cmp(const void* a, const void* b);
int partition(int n, int s, int e);

int main(){
    int n,s,i,j;
    scanf("%d %d",&n,&s);
    for(i=0;i<n;i++){
        scanf("%d %d",&arr[i].height,&arr[i].price);
    }
    qsort(arr, n, sizeof(Pic), cmp);

    int max = 0;
    dp[0] = arr[0].price;
    int m = 0;
    int max_index = 0;
    int now_max = 0;
    for(i=1;i<n;i++){
        while(arr[i].height - arr[m].height >= s && m <= i){
            if(now_max < dp[m]){ // m이전까지 최대이익을 갖는 인덱스 최신화
                now_max = dp[m];
                max_index = m;
            }
            m++; // m전까지가 해당그림과 겹치지 않는 그림들이다.
        }
        dp[i] = now_max + arr[i].price;
    }
    for(i=m;i<n;i++){
        if(now_max < dp[i]){
            now_max = dp[i];
        }
    }
    printf("%d",now_max);
}

int cmp(const void* a, const void* b){
    return (*(Pic*)a).height > (*(Pic*)b).height;
}

위 코드에서 while문이 현재 i 값을 기준으로 노란그림들의 구역을 나눠주는 역할을 하고 m 이라는 변수가 가장 최초의 빨간그림 인덱스를 말한다. 위 예시에서는 dp[4] 를 구할때 m은 3이된다.

 

그리고 현재까지의 최대값(노란그림들중)을 나타내는 변수인 now_max값은 노란그림들까지만 고려한 변수이고 마지막에 for문이 끝나면 끝나기 직전에 빨간그림들까지는 고려해주지 못하므로 마지막에 빨간그림들영역을 for문으로 한번 돌면서 최종적으로 최대 총합을 계산하게 된다.

 

---

WHY : dp[i]의 조합이 dp[i+k]를 고려할때도 과연 dp[i]가 최선의 선택이였는가?

 

이 문제는 점화식을 설계할때 해당 i 번째 그림을 선택할때 어디까지가 독립적이고 어디까지가 독립적이지 않은지 판단하는것이 중요했다. 사실 이 점화식을 세우면서 헷갈렸던 부분은 dp[i]를 i까지 그림들중 i번째 그림을 무조건 선택할때 최대값이라고 했을때, 가능한 모든 경우의 수들이 다 고려되는것인지 의문이 들었고, dp[i]의 조합이 dp[i+k]를 고려할때도 과연 dp[i]가 최선의 선택이였는가? 이런부분이 의문이 들었었다. 

 

어떤 의미냐면, 만약 k그림 이전까지 가능했던 조합이 A가지이고 k이전 dp[i] (i < k) 들의 조합을 P, 그 외의 조합들을 Q라고 하자. 현재 dp를 구하는 과정은 dp[k]를 구할때 P 의 원소들 중에 k번째 그림을 포함해서 최선의 결과가 dp[k]에 담긴다. 그러나 만약 Q의 조합들중 하나와 k가 결합해서 최선의 결과가 나올수 있지 않을까?

 

이부분은 dp[k] 까지 진행했을때 dp[k+1]은 k그림까지의 모든 경우들중 최선의 결과를 따라간다. 이유는 만약 Q 조합중 하나인 q가 있고 그 q조합에서마지막에 k 그림을 포함했을때 최선의 결과가 나왔다고 가정해보자. 이 q에서 마지막 그림의 인덱스가 j라고 하면, 마지막그림을 j로 하는 최선의 조합 + 마지막에 k를 놓는것인데, 여기서 "마지막그림을 j로 하는 최선의 조합" 이라는 뜻은 사실 dp[j] 를 의미한다. 따라서 이 dp[j]는 Q집합이 아닌 P집합에 속해야 하므로 거짓이다.