전깃줄 (1) 썸네일형 리스트형 [BOJ] 2565 전깃줄/Dynamic Programming/이분 탐색/최장 증가 부분 수열(LIS)/C++ 풀이 문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 문제에서 제시해준 예제를 통해 풀이를 생각했다. 위 처럼 전깃줄 개수가 처음에 주어지고 그 다음 (시작 전봇대 위치 - 끝 전봇대 위치)들이 주어진다. 시작 위치 기준으로 정렬한다면 다음과 같이 된다. 이 때 문제의 예시의 답에서 알려준 끝 전봇대 위치가 1, 8, 9인 전깃줄을 제외하고 관찰해보면 흥미로운 특징이 보인다. 바로 2, 4, 6, 7, 10은 증가하는 수열이라는 것이다. 시작 전.. 이전 1 다음
