흙금이네 블로그

아이디어 전깃줄이 교차하지 않으려면 전깃줄들이 연결된 A의 위치 값이 증가할 때 B의 위치 값도 증가해야 한다. 따라서 전깃줄들을 A의 위치 값 기준으로 오름차순으로 정렬하고, B의 위치 값이 증가하는 가장 긴 수열의 길이를 구한다. 풀이 전깃줄이 연결된 A의 위치 값과 B의 위치 값을 튜플로 리스트 line에 저장하고, line을 오름차순 정렬한다. 1로 채워진 N 크기의 리스트 dp를 생성하고, dp에 증가하는 수열의 가장 긴 길이를 저장해 나간다. j 번째 전깃줄이 연결된 B의 위치 값이 i 번째 전깃줄이 연결된 B의 위치 값보다 크고, dp[i]+1와 비교해 dp[j]를 갱신한다. 마지막에 전체 전깃줄 개수 N에서 가장 긴 증가하는 수열의 길이 max(dp)를 뺀 값을 출력한다. import sy..