[BOJ] 2515 전시장

이 문제도 다이나믹(DP) 문제이다.

제일 먼저 생각한 것은

그림들을 높이 순으로 오름차순 정렬시키는 것이다.

판매가능 그림의 조건이 부분적으로 S이상만큼만 보이면 되기에

최대한 그림의 높이가 낮은것부터 높은 순으로 배치하면 판매가능 그림의 갯수가 많아질 것이기 때문이다.

이를 기본 전제로 깔고 가면서

각 그림의 높이와 가격을 비교하며 최대합을 구해야 한다.

캐싱할 DP 배열의 값은 각 그림이 배치될 때 구할 수 있는 가격의 최대합이다.

그리고 각 그림별로 순회하면서 이전 그림들과의 높이 차를 비교하면서

가격의 합을 비교, 저장하면 되겠다 생각했는데....

처음부터 잘 풀려고 하면 힘드니 일단 쉽게 풀 수 있으나 무식하게 시간초과 나는 코드를 짜보았다.

  

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <string>
#include <random>
#include <string.h> //gcc memset
#include <math.h>
using namespace std;
 
int N = 0, S = 0; //그림의 갯수, 판매가능 그림의 보여지는 최소높이
vector< pair<int, int> > pictures; //전시할 그림들 정보 (pair first = 높이, second = 가격)
int DP[300001]; //DP[N] = N번째 그림에서 가능한 최대합
int _max(int a, int b) { return (a > b) ? a : b; }
 
//정렬 함수, 그림들의 가격을 기준으로 오름차순 정렬
bool sortFunc(const pair<int, int>& left, const pair<int, int>& right)
{
    return (left.first < right.first);
}
//동적계획법을 활용하여 답 구하기
int solve()
{
    int retVal = 0;
    //DP 초기화
    memset(DP, 0, sizeof(DP));
    DP[0] = pictures[0].second; //DP 초기값으로 제일 작은 그림의 가격을 세팅
 
    //이전 DP 비교체크를 위한 루프 하한선 (매번 N-1 ~ 0까지 돌리기는 비효율적임) 
    int prevCheckBorder = 0;
    //DP[0]이 세팅된 상태여서 1부터 순회
    for (int k = 1; k < N; ++k)
    {
        //현재 k번째의 이전 그림들을 체크하며 k번째에서의 최대합을 구해준다.
        for (int m = k - 1; m >= 0; --m)
        {
            //높이 차를 체크 (k번째 그림에 얼만큼 부분적으로 보여지는가)
            int diffH = pictures[k].first - pictures[m].first;
            //높이 차가 S이상이면 판매가능 그림이므로,
            //k번째 저장된 최대합과 (이전 그림에 저장된 최대합 + k번째 그림)을 비교
            if (diffH >= S)
            {
                if (DP[k] < DP[m] + pictures[k].second)
                    DP[k] = DP[m] + pictures[k].second;
            }
            //높이 차가 S이하면 k번째 그림에 아예 가려지기에 k번째 그림의 가격을 더할 수 없다.
            //그냥 현재 k번째 그림 가격과 이전 DP값 비교해서 최대값 갱신만 함
            else
                DP[k] = _max(DP[k], _max(DP[m], pictures[k].second));
        }
        //다음 루프에서 사용할 루프 하한선 갱신
        prevCheckBorder = calcCheckBorder;
    }
 
    //마지막 그림에 누적된 최대합 리턴
    return DP[N - 1];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> N >> S;
    int x = 0, y = 0;
 
    for (x = 0; x < N; ++x)
    {
        int H = 0, C = 0;
        cin >> H >> C;
        pictures.push_back(make_pair(H, C));
    }
    //그림들을 일단 높이 순으로 정렬
    sort(pictures.begin(), pictures.end(), sortFunc);
 
    //solve 함수로 리턴된 결과 값 출력
    cout << solve() << "\n";
    return 0;
}

Line 35,38을 보면, 매 그림들을 순회할 때마다 이전 그림들을 전부 순회 하면서

높이 차를 비교하여 DP 캐시를 갱신하는 식으로 진행하였다.

답이 나오긴 하지만 문제는 시간 복잡도다.

기본적으로 N에 대한 루프를 돌리고

안쪽 루프에선 이전 그림들과 비교를 위해 N-1 ~ 0까지 일일이 돌리기 때문에

O(N^2)의 복잡도를 가지게 되며, 문제에선 N=300000이 최대이기에

300000^2 = 900억에 가까운 어마어마한 루프 횟수가 나온다... 

사실 정확히 따져보면

N=300000이면

안쪽 루프에서 300000회, 299999회, 299998회.... 를 쭉 더해준 것.

즉, 1부터 300000까지의 합을 구한 것이 총 루프 횟수가 되겠다.

n(n+1) / 2 식을 이용하면 300000 * 300001 / 2 = 45,000,150,000 (약 450억)

그래봤자 n^2이 어마어마해서 1/2 해도 뭐 헤헤.....

그래서 다른 효율적인 방법을 강구해보았다.

어차피 매 그림마다 가격의 최대합을 누적시켜 DP에 저장하기에

위 코드처럼 이전 그림들의 DP를 일일이 다 비교하는 것은 어찌보면 불필요한 연산을 수행하는 것이다.

이전 그림들에서 이미 계산된 합들이 저장되고 있어서 이전 그림들 중 일부만 비교하면 될 거라는 생각을 해본다.

그 비교 대상은

1. 현재 그림에서 높이차가 S이상인 가장 높이가 큰 그림의 DP + 현재 그림의 가격

2. 이전 그림의 DP

이 두 정보만 있으면 된다.

여기서 1.의 '현재 그림에서 높이차가 S이상인 가장 높이가 큰 그림의 DP' 를 어떻게 찾을까?

위의 시간초과 코드에서처럼 이전 그림들을 일일이 선형탐색하는 것이 아니라

이분탐색 (Binary Search)를 활용하여 조건에 맞는 그림을 빠르게 찾아주자는 것이다.

이분탐색의 시간복잡도가 O(log n)이기에 선형탐색보단 효율이 좋다.

위의 아이디어를 바탕으로 재구현한 코드는 아래와 같다. (AC 받음)

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <string>
#include <random>
#include <string.h> //gcc memset
#include <math.h>
using namespace std;
 
int N = 0, S = 0; //그림의 갯수, 판매가능 그림의 보여지는 최소높이
vector< pair<int, int> > pictures; //전시할 그림들 정보 (pair first = 높이, second = 가격)
int DP[300001]; //DP[N] = N번째 그림에서 가능한 최대합
int _max(int a, int b) { return (a > b) ? a : b; }
 
//정렬 함수, 그림들의 높이를 기준으로 오름차순 정렬. 높이가 같으면 가격을 오름차순
bool sortFunc(const pair<int, int>& left, const pair<int, int>& right)
{
    if (left.first == right.first)
        return left.second < right.second;
    return left.first < right.first;
}
//curPic 인덱스의 그림과 S이상 차이나는 제일 가까운 그림을 찾는 이분탐색 함수
int bSearch(int curPic)
{
    //0 ~ curPic 범위로 세팅
    int mid = 0, left = 0, right = curPic;
    while (left <= right)
    {
        mid = (left + right) / 2;
        //curPic과 현재 mid의 높이차를 구함
        int diff = pictures[curPic].first - pictures[mid].first;
        //높이차가 S이상이면 오른쪽 방향으로 범위를 줄인다.
        if (diff >= S) left = mid + 1;
        //S 미만이면 왼쪽 방향으로 범위를 줄인다.
        else right = mid - 1;
    }
    //조건을 만족하면서 curPic에 제일 가까운 인덱스를 리턴 
    return right;
}
//동적계획법을 활용하여 답 구하기
int solve()
{
    //DP 초기화
    memset(DP, 0, sizeof(DP));
    DP[0] = pictures[0].second;
 
    //DP[0]이 세팅된 상태여서 1부터 순회
    for (int k = 1; k < N; ++k)
    {
        //k번째 그림에서 높이차가 S이상인 가장 가까운 그림을 찾음
        int findLastShow = bSearch(k);
        //찾았다면 (해당 그림의 최대합 + 현재 그림의 가격), (이전 그림의 최대합)과 비교
        if (findLastShow > -1)
            DP[k] = _max(DP[findLastShow] + pictures[k].second, DP[k - 1]);
        //못 찾았음 (현재 그림의 가격), (이전 그림의 최대합)을 비교
        else
            DP[k] = _max(DP[k - 1], pictures[k].second);
    }
 
    //마지막 그림에 누적된 최대합 리턴
    return DP[N - 1];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> N >> S;
    for (int x = 0; x < N; ++x)
    {
        int H = 0, C = 0;
        cin >> H >> C;
        pictures.push_back(make_pair(H, C));
    }
    //그림들을 위 정렬함수를 통해 정렬
    sort(pictures.begin(), pictures.end(), sortFunc);
    //solve 함수로 리턴된 결과 값 출력
    cout << solve() << "\n";
    return 0;
}