lis (1) 썸네일형 리스트형 [BOJ 16474] 이상한 전깃줄 https://www.acmicpc.net/problem/16474 16474번: 이상한 전깃줄 엘리트 도로설계사 현정이는 도로 위 전봇대 사이에 연결된 전깃줄을 관리하는 일을 한다. 도로 양 옆에는 각 고유번호를 갖고 있는 전봇대가 여러 개 있다. 마을에 최대한 많은 양의 전력을 보 www.acmicpc.net Tag : lis 문제요약 전깃줄의 연결 상태가 입력으로 들어오는데 이 때 전깃줄을 최소한으로 끊어서 전깃줄이 교차하지 않는 상태를 만드는 것이 목표이다. 전깃줄을 끊는 최소 횟수를 구하라. 풀이 입력을 조금만 손보면 \(O(N^2)\) lis 문제가 된다. 전체코드 #include "bits/stdc++.h" #define endl '\n' using namespace std; using ll.. 이전 1 다음