[BOJ 8984] 막대기

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

8984번: 막대기

 

- 문제 요약

 

다양한 길이의 막대기를 가지고 즐길 수 있는 게임이 있다. 게임을 시작하기 전에 간격이 L인 두 개의 평행한 수평선을 책상 위에 긋고, 막대기의 양 끝이 각 수평선에 하나씩 위치하도록 놓는다. 여러 개의 막대기 끝이 수평선 위의 한 점에서 만날 수는 있지만, 두 막대기가 완전히 겹쳐져 있는 경우는 없다. 놓여 있는 각 막대기는 (t, d)로 표현된다. 여기서 t는 위쪽 수평선에서의 좌표이고 d는 아래쪽 수평선에서의 좌표이다. 아래 그림 1에서 막대기 a는 (1, 0), 막대기 b는 (6, 0)으로 표시된다.

게임은 책상에 놓여 있는 막대기들 중 일부를 들어내어 남아 있는 막대기들이 다음의 세 조건을 모두 만족하는 하나의 지그재그 선이 구성되도록 하는 것이다: (1) 막대기들은 끝점을 제외하곤 서로 교차하지 않는다. (2) 세 개 이상의 막대기 끝이 한 점에서 만나지 않는다. (3) 모든 막대기는 연결되어 있다.

이 게임의 승자는 길이가 가장 긴 지그재그 선을 만든 사람이다. 지그재그 선의 길이는 막대기 길이들의 합이며, 각 막대기의 길이는 양 끝점의 수평 거리와 수직 거리를 더한 값으로 계산한다. 즉, 막대기 (t, d)의 수평 거리는 t와 d 사이의 절댓값 |t-d|이고, 수직 거리는 두 수평선 사이의 간격인 L이다. 위 그림에서 각 막대기의 길이는 다음과 같다.

예를 들면, 그림 1에서 막대기 a, b, e 만 남겨진 경우는 세 조건을 모두 만족하는 지그재그 선이 며, 길이는 17 = 4+9+4이다. 막대기 c, e 만 남겨진 경우도 세 조건을 모두 만족하는 지그재그 선이며, 길이는 10 = 6+4이다. 막대기 b, c 만 남겨진 경우는 조건 (1)에 위배되고, 막대기 c, d, e 만 남겨진 경우는 조건 (2)에 위배되고, 막대기 a, b, g 만 남겨진 경우는 조건 (3)에 위배된다. 길이가 가장 긴 지그재그 선은 막대기 c, d, f, g로 구성되며, 길이는 20 = 6+4+7+3이다.

막대기들의 초기 상태가 주어져 있을 때, 가장 긴 지그재그 선의 길이를 구하기 위한 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

dp[i][j] = j번째 선의 i번 좌표에서 끝나는 지그재그 선의 최대 길이

위와 같이 점화식을 만들고 막대를 좌표에 대해 오름차순으로 정렬합니다.

그리고 순서대로 막대를 확인하며 DP Table을 갱신해 줍니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100001
typedef long long ll;
int n,l,t,d;
ll result,dp[MAX][2];
vector<int>v[2];
vector<pair<int,int> >edge;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>l;
    for(int i=0;i<n;i++){
        cin>>t>>d;
        edge.push_back({t,d});
        v[0].push_back(t);
        v[1].push_back(d);
    }
    sort(edge.begin(),edge.end());
    sort(v[0].begin(),v[0].end());
    sort(v[1].begin(),v[1].end());
    v[0].erase(unique(v[0].begin(),v[0].end()),v[0].end());
    v[1].erase(unique(v[1].begin(),v[1].end()),v[1].end());
    for(int i=0;i<n;i++){
        pair<int,int>cur=edge[i];
        int idx0=lower_bound(v[0].begin(),v[0].end(),cur.first)-v[0].begin();
        int idx1=lower_bound(v[1].begin(),v[1].end(),cur.second)-v[1].begin();
        int len=abs(cur.first-cur.second)+l;
        ll tmp0=dp[idx0][0],tmp1=dp[idx1][1];
        dp[idx0][0]=max(dp[idx0][0],tmp1+len);
        dp[idx1][1]=max(dp[idx1][1],tmp0+len); 
        result=max({result,dp[idx0][0],dp[idx1][1]});
    }
    cout<<result;
}

코드 제출 결과