BOJ[백준] - 8984 - 막대기

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

 

문제의 예제 입력을 가지고 봅시다..

(1) stick 배열에 넣고, 정렬   {<1,0>, <2,5>, <4,5>, <4,8>, <6,0>, <6,5>, <8,8>}

(2) t만 넣은 vector = tv 와 d만 넣은 vector dv 에서 unique()와 erase() 를 이용하여 중복되는 값을 전부 제거하면 다음과 같습니다.

tv { 1, 2, 4, 6, 8 }  -> 그림으로 보면 윗 줄엔  5개 점,  아래쪽 줄에는.. 3개점만 있는거죠..!

dv { 0, 5, 8 }

(3) DP 배열을 준비해 봅니다.

(4) 이제 준비는 끝났습니다. T_dp[x] 는 tv의 x번째 항목에 해당하는 좌표의 점으로 끝나는 zig-zag의 MAX길이가 되네요..

결국 결과는 아래와 같네요 !  D_dp[1] 은 dv의 1번 idx, 즉, d가 5번 좌표인 점으로 끝나는 지그재그의 길이는 a, b, e를 선택했을 때니까 17이 맞습니다.

T_dp[0] = 4, [1] = 6, [2] = 10, [3] = 13, [4] = 20

D_dp[0] = 9, [1] = 17, [2] = 17

 

답은 zig-zag의 최대값이므로 20입니다.

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int MXN = 100001;
int N, L;
long long T_dp[MXN];
long long D_dp[MXN];
pair<int,int> stick[MXN];
vector<int> tv, dv;
 
int main()
{
   scanf("%d%d", &N, &L);
   for(int i = 0; i<N; i++)
   {
      scanf("%d%d", &stick[i].first, &stick[i].second);  // <t,d> pair
      tv.push_back(stick[i].first);
      dv.push_back(stick[i].second);
   }
   sort(stick, stick + N);
   sort(tv.begin(), tv.end());
   sort(dv.begin(), dv.end());
   // eliminate the duplicated values & reduce the size of each vector
   tv.erase( unique(tv.begin(), tv.end()), tv.end() );
   dv.erase( unique(dv.begin(), dv.end()), dv.end() );
   long long ans = 0;
   for(int i = 0; i < N; i++)
   {
      int t_idx = lower_bound(tv.begin(), tv.end(), stick[i].first) - tv.begin();
      int d_idx = lower_bound(dv.begin(), dv.end(), stick[i].second) - dv.begin();
      int len = L + (abs(stick[i].first - stick[i].second));
      long long t = T_dp[t_idx], d = D_dp[d_idx];
      // (T_dp, D_dp) array has the maximum length of zig-zag pattern ending with the point(t & d vector). 
      T_dp[t_idx] = max(t, d + len);
      D_dp[d_idx] = max(d, t + len);
      ans = max(T_dp[t_idx], max(ans, D_dp[d_idx]));
   }
   printf("%lld",ans);
   return 0;
}