[백준] 1365번 꼬인 전깃줄 문제 풀이(c++)

문제 링크 - https://www.acmicpc.net/problem/1365

1365번: 꼬인 전깃줄

문제 설명

공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다.

문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다.

임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다.

유스타운 시의 시장 임한수를 도와 잘라내야 할 전선의 최소 개수를 구하는 프로그램을 작성하시오.

 

아이디어

전선이 꼬이지 않도록 최대의 전봇대가 서 있기 위해서는 전봇대의 값들이 가장 긴 오름차순의 형태로 이루어져 있어야 한다.

이 말은 최장 증가 부분 수열을 찾아야 한다는 의미와 같다.

따라서, 전체 전선의 개수에서 최장 증가 부분 수열의 길이를 빼면 전선을 꼬이게 만드는(최장 증가 부분 수열에 포함되지 않는) 전깃줄의 개수를 알 수 있는 것이다.

 

https://nomadsjh.tistory.com/66

[백준] 12015번 가장 긴 증가하는 부분 수열2 문제 풀이(c++)

위 문제를 해결하는 코드의 출력만 바꿔주면 이 1365번 문제를 풀 수 있다.

소스코드

#include <bits/stdc++.h>
using namespace std;
int arr[1000001];
vector<int>v;

int main()
{
    int N; scanf("%d %d",&N,&arr[0]);

    v.push_back(arr[0]);
    for(int i=1;i<N;i++)
    {
        scanf("%d",&arr[i]);
        if(v.back()<arr[i])
        {
            v.push_back(arr[i]);
        }
        else
        {
            int index=(lower_bound(v.begin(),v.end(),arr[i])-v.begin());
            v[index] = arr[i];
        }
    }
    printf("%d",N-v.size());
}