프로그래밍에 대한 고찰 및 생각

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

알고리즘/백준

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

Source 2020. 2. 24. 02:17

 

 


문제이해

문제에서는 총 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집합에 속해야 하므로 거짓이다.