줄세우기
-
백준 2631번 줄세우기 [LIS] :: 마이구미알고리즘 풀이/동적계획법 2017. 4. 2. 00:33
이번 글은 백준 알고리즘 2631번 "줄세우기" 를 다뤄본다.이 문제는 LIS 알고리즘을 활용하여 해결할 수 있다. LIS 알고리즘, 최장증가수열은 본인이 다른 글에서 이미 다뤘었다.모른다면, 참고하고 읽으면 도움이 될 것이다. (LIS 알고리즘 관련글) 왜 LIS 알고리즘을 활용할 수 있는 지 문제를 보며 설명하겠다. KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리..