백준 2565번: 전깃줄(C++)

www.acmicpc.net/problem/2565

2565번: 전깃줄

코드

#include <iostream>
using namespace std;

int line[501] = {0, };
int dp[501] = {0, };
int n;
int min_idx = 1000;
int max_idx = -1000;
void init(){
  cin >> n;
  int idx;
  for(int i=0; i<n; i++){
    cin >> idx;
    min_idx = idx < min_idx ? idx : min_idx;
    max_idx = idx > max_idx ? idx : max_idx;
    cin >> line[idx];
  }
}

void solve(){
  int max_num = 0;
  for(int i=min_idx; i<=max_idx; i++){
    if(line[i] == 0) dp[i] = 0;
    else dp[i] = 1;
    for(int j=min_idx; j<i; j++){
      if(line[i] > line[j]){
        dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;}
      }
      max_num = dp[i] > max_num ? dp[i] : max_num;
    }
    cout << (n - max_num);
}

int main(){
  init();
  solve();
}

풀이

괜히 어... 전깃줄이 교차되어있고... 그럼 이걸 제거하는게 더 이득인가 저걸 제거하는게 이득인가..?

재면서 생각하면 더 어려운 문제입니다. 간단하게 생각하시면 이전에 푼 '가장 긴 증가하는 수열' 과 같습니다.

wonsang98.tistory.com/77

백준 11053번: 가장 긴 증가하는 부분 수열(C++)

 

무슨 의미냐 하면

주어진 N 개의 전깃줄이 있습니다. 문제의 입출력 예시에 따르면 

8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

이 입력이 되며, 이 입력에 따른 입력결과는 아래 그림과 같습니다.

배열로 치면 A는 배열의 index라 하고, B는 index에 대응되는 값이라고 하겠습니다. (배열 arr[Ai] = Bi)

그렇다면 배열은 이렇게 정리가 되겠죠.

이제 간단합니다. 가장 작은 idx ~ 가장 큰 idx 내에서 '가장 긴 증가하는 부분 수열'의 길이를 구한 후

주어진 전깃줄의 수 N에서 빼주면 정답이 됩니다. 

증가하는 부분 수열은 곧, 전깃줄이 겹치지 않게 배열하는 것 중 가장 긴 수열과 같기 때문입니다.