[알고리즘] 백준 2565

아래 정리하는 내용들은 대부분 다른 분들의 코드를 참고하여 작성한 코드이기 때문에 최적화 되어 있지 않으며 개인적으로 기억하기 위한 용도입니다. 혹시 문제 풀이를 위해서 검색하신 분들께서는 참고 수준으로만 읽어보시기 바랍니다. References https://swexpertacademy.com/ https://www.acmicpc.net/ https://leetcode.com/ 추천 블로그 https://zoosso.tistory.com/ 이번 문제는 최장 증가 수열 (LIS) 문제로 서로 전기줄이 겹쳐지지 않게 최대 개수의 전기줄을 설치하는 문제이다. 아래 그림에서 i 번째 지점에서 이미 전기줄이 배치되어 있다고 할 때, i 보다 작은 j 지점 전기줄의 오른쪽 위치는 i 번째 전기줄의 오른쪽 위치보다 값이 작아야 겹쳐지지 않게된다. 문제 풀이를 위해서는 우선 left, right 로 구성된 전기줄 line 리스트를 left 점 기준으로 정렬한다. dp[i] 는 1로 초기화 된 상...

원문링크 : [알고리즘] 백준 2565