어흥

문제 링크: www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 1. 주의할 점 - LIS(가장 증가하는 부분수열)에 대해 알고 있어야 한다 2. 구현 - 모든 수에 대한 입력을 Arr[] 배열에 받는다 - DP[idx] 배열 통해 가장 긴 증가하는 부분 수열을 나타낼 때, idx번째로 작은 수를 DP[idx]에 저장한다 - 만약 새로 비교하는 값(Arr[i])가 DP[] 배열의 가장 마지막 원소(DP[idx])보다 크면, DP배열에 새로 추가한다..