백준/Platinum(1~5) (1) 썸네일형 리스트형 [백준]_2568번 : 전깃줄 - 2(파이썬) 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 일단 아이디어 자체는 전깃줄과 다를 바가 없다. 꼬인 전깃줄을 꼬이지 않게 하기 위해서는 전깃줄을 하나의 쌍(예를 들어 [1, 8])으로 묶은 다음에 첫 번째 요소에 대해 정렬을 진행한 다음에 두 번째 요소의 LIS(최장 부분 수열)를 구하면 된다. 애초에 전깃줄의 꼬임이 왜 발생하는지에 대해 생각해 보면 이해하기 수월해진다. 전깃줄은 다음과 같은 조건을 만족시킬 때 꼬인다. 왼쪽 전봇대의 전깃줄을 a1, b1 이라고 하고 그에 대응하는(이어져 있는) 오른쪽.. 이전 1 다음
