[백준] 2565 전깃줄 c++
문제 링크 https://www.acmicpc.net/problem/2565 KEY 문제에서 없애야 하는 전깃줄의 최소 갯수를 구하라는 말은, 전깃줄의 전체 갯수 - 엉키지 않도록 하는 전깃줄의 최대 갯수를 구하라는 말과 동일하다. 입력값의 first를 기준으로 오름차순 정렬을 하면 first를 고정시킬 수 있으므로 second만 고려할 수 있다. 문제의 예제를 살펴보면, 정렬 후 second는 8, 2, 9, 1, 4, 6, 7, 10로 나타난다. 여기서 8, 9, 1을 없앤다면 2,4,6,7,10이 될 것이고, 이는 엉키지 않도록 하는 전깃줄의 최대 갯수가 된다. 따라서, 순열이 주어졌을 때, 가장 긴 증가하는 부분수열의 길이를 구한 후, 전체 갯수 N에서 빼주면 없애야 하는 전깃줄의 최소 갯수가 나..
2023. 3. 28.
