문제 설명 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 자세한 문제 설명은 위 링크를 참고하시길 바랍니다. 풀이 과정 이 문제는 DP(다이나믹 프로그래밍)을 이용해 최대 증가 수열을 찾는 문제라고 할 수 있다. 전깃줄이 교차하지 않도록 하려면 어떻게 해야할지에 대해 먼저 생각해보자. 먼저, 위 그림에서 A의 1번과 B의 8번만 연결되어 있다고 가정해보자. 그리고 이 때, 아래의 ①번 상황과 ②번 상황을 각각 생각해보자. ① A의 2번과 B의 2번이..