Heecheol's blog

문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 이 문제를 처음 봤을 땐, 어떻게 dp로 풀어야하는지 전혀 감이 안왔다. 그래서 검색을 해보니 LIS와 관련이 있다고했다. LIS란 최장 증가 부분 수열이라는 의미로, 말그대로 배열 안에서 증가하는 부분 수열중 가장 긴 수열을 의미한다. 예를 들어, [1,4,5,3,8,6,9]라는 arr배열이 있을 때 최장 증가 부분 수열은 [1,4,5,6,9]를 나타낸다. LIS를 구할 때 dp가 사용되는 ..