백준, BOJ, 2565번, 전깃줄 : C++ [CPP]

 

증가수열과 비슷하다.

여기서 전깃줄이 겹칠 때 어떨 때 겹칠까 생각해보면 된다.

 

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

---

#맞은 풀이

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


//A가 내가 고르는 것 B가 결과라고 해보자
//내가 고른 것이 이전에 고른 것의 결과보다 작아선 안된다.
//다음 것은 내가 고른 것의 결과보다 항상 커야한다.
//1번줄을 연결해서 2번줄의 결과를 얻었다면
//2번줄을 연결했을 때 2번보다 작은 결과를 얻어서는 안된다.

//내가 순서대로 고르고 결과만 위의 조건에 맞게 하면 되겠다.
//-> 전깃줄 순서대로 정렬

//전깃줄을 삭제하는 방법이 아닌 최대의 전깃줄 연결 방법
//-> 최대 5개의 전깃줄을 연결할 수 있다 == 설치한 전깃줄 - 최소로 제거하는 전깃줄

int N;

vector <pair<int, int>> vec;

int arr[101];
int dp[101]; //결괏값들의 최대 부분 증가 수열

int main() {

    cin >> N;

    for (int i = 0; i < N; i++) {
        int from, to;
        cin >> from >> to;
        vec.push_back({ from, to });
    }

    //from 기준으로 오름차순 정렬
    sort(vec.begin(), vec.end());

    //dp초기화
    fill(dp, dp + 101, 1); //자기 자신을 항상 포함하므로 1의 최소 크기를 가짐

    //결괏값들을 내가 고른 전깃줄의 오름차순으로 배열에 집어넣음
    int cnt = 1;
    for (auto x : vec) {
        arr[cnt++] = x.second;
    }

    int ans = 0;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }


    cout << N - ans;


    return 0;
}

 

사실 겹친다는 것의 의미는

 

내가 이전에 결과보다 이번의 결과가 더 작다는 말이다.

즉, 겹치지 않으려면 이전의 결과보다 커야 한다는 말이다(중복이 안되니까)

이 말이 알고보니 결괏값이 증가수열로 나와야 한다는 의미고

최대 증가 부분 수열을 구하라는 의미였다.

 

문제 속에서 이것을 알아냈다면 쉽게 풀 수 있었겠지만..

저렇게까지 바로 이해하기는 쉽지 않다.