백준 25651 2565. 전깃줄 (Python) 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 최장 증가 부분 수열을 활용하여 해결할 수 있다. 최장 증가 부분 수열에 관한 설명은 여기를 참고하자. A 전봇대의 1번부터 N번까지 연결되어 있는 B의 전깃줄 번호를 한 배열 안에 담아둔다. 그 배열 안에서 최장 증가 부분 수열의 길이를 구하고 이를 N에서 빼주면 없애야 하는 전깃줄의 최소 개수를 구할 수 있다. 코드 import heapq from bisect import bisect_left if __name__ == '__main__': N = int(in.. 2022. 5. 21. 이전 1 다음
