[PS] 백준 8984번: 막대기

|

문제

내가 이해한 문제 내용

여러개의 막대기가 임의의 배치로 주어질 때 지그재그 모양의 막대기 중 가장 긴 길이를 구하시오.

접근 방식

  • DP라는 것을 캐치하고 수십개의 막대기를 그려본 결과 다음과 같은 점화식을 얻었다.
    • dp[0][i]=i번째 막대기가 위쪽에서 시작할 경우의 최대길이
    • dp[1][i]=i번째 막대기가 아래쪽에서 시작할 경우의 최대길이
    • 위와 같이 정의하고 막대기가 주어지면 위쪽 수직선 기준으로 정렬한 후에 dp를 돌렸지만 시간초과.
    • 고민하다가 더 이상은 시간낭비인 것 같아 답을 봤다.
  • 풀이의 접근방식
    • 제일 중요한 관찰은 특정 점에 중복되는 막대기를 제거하는 것인데 그 이유는 해당 점에 아무리 막대기가 많다 하더라도 최대 길이만 찾으면 되기 때문이다.
    • 이제 위쪽과 아래쪽을 각각 정렬하여 따로 dp 식을 구성한다.
    • 주어진 입력을 돌면서 위쪽 좌표와 아래쪽 좌표에 대해 정렬한 배열에서 해당하는 인덱스를 찾는다.
    • 반복하면서 dp 식을 업데이트 해주면 된다.
    • t_dp[i]=위쪽 수직선에서 i번째 좌표로 시작하는 막대기 길이의 최댓값
    • d_dp[i]=아래쪽 수직선에서 i번째 좌표로 시작하는 막대기 길이의 최댓값

어려웠던 점 & 배운 점

  • 시간초과가 발생하고 나서 이분탐색을 쓰려고 했으나 특정 좌표에 해당하는 막대기 길이의 최댓값을 찾아야 했기 때문에 불가능해서 어려웠다.
  • 위쪽 수직선과 아래쪽 수직선을 나눠서 접근하는 방식이 난해했고 나눈 상태에서 점화식을 세울 수 없었다.
  • 풀이에선 벡터의 함수를 사용해서 중복을 제거하지만 이분탐색으로 해결할 수 있다.

시간복잡도

  • $O(NlgN)$

코드

코드는 거의 비슷하지만 그래도 다시 혼자 힘으로 구현했기에 첨부한다.

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int MAX_SIZE = 100005;

pii stick[MAX_SIZE];
int top[MAX_SIZE],down[MAX_SIZE];
ll tdp[MAX_SIZE],ddp[MAX_SIZE];
vector<int> rtop,rdown;
int N,L;

bool findValue(int left, int right, int target, vector<int>& vec) {
    while(left<=right) {
        int m = (left+right)/2;
        if(target<vec[m]) right = m-1;
        else if(target>vec[m]) left = m+1;
        else return true;
    }
    return false;
}

int main(void)
{
    scanf("%d%d",&N,&L);

    for(int i=1; i<=N; i++) {
        scanf("%d%d",&stick[i].first,&stick[i].second);
        top[i] = stick[i].first;
        down[i] = stick[i].second;
    }

    sort(stick+1,stick+N+1);
    sort(top+1,top+N+1);
    sort(down+1,down+N+1);

    rtop.push_back(top[1]);
    rdown.push_back(down[1]);
    for(int i=2; i<=N; i++) {
        if(!findValue(0,rtop.size()-1,top[i],rtop)) {
            rtop.push_back(top[i]);
        } 
        if(!findValue(0,rdown.size()-1,down[i],rdown)) {
            rdown.push_back(down[i]);
        }
    }

    ll ans = 0LL;
    for(int i=1; i<=N; i++) {
        int tidx = lower_bound(rtop.begin(),rtop.end(),stick[i].first) - rtop.begin();
        int didx = lower_bound(rdown.begin(),rdown.end(),stick[i].second) - rdown.begin();

        ll len = abs(rtop[tidx]-rdown[didx]) + L;
        ll ttemp = tdp[tidx];
        ll dtemp = ddp[didx];
        tdp[tidx] = max(ttemp, dtemp+len);
        ddp[didx] = max(dtemp, ttemp+len);
        ans = max(ans,max(tdp[tidx],ddp[didx]));
    }

    printf("%lld",ans);

    return 0;
}