[ BOJ 백준 1365번 - 꼬인 전깃줄 ] 해설 및 코드

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

 

목적

왼편과 오른편의 전봇대에 연결된 전선을 꼬이지 않게 하기 위해 끊어야하는 최소 전선의 개수를 구하자.

 

접근법

1. LIS를 활용하여 접근한다. 결국은 N에서 가장 긴 부분 증가 수열의 길이를 빼면 답이 도출된다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n;cin>>n;
    vector<int> v;
    f(i,0,n){
        int num;cin>>num;
        int pos=lower_bound(v.begin(), v.end(), num)-v.begin();
        if(pos==v.size())v.push_back(num);
        else if(v[pos]>num)v[pos]=num;
    }
    cout<<n-v.size()<<'\n';
    
    return 0;
}
 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.