반갑습니다!

[백준] 2631줄 세우기 본문

알고리즘 문제 풀이

[백준] 2631줄 세우기

김덜덜이 2020. 10. 22. 15:28

풀이

이 문제는 LIS 알고리즘을 통해 해결할 수 있다.

키 순서가 오름차순으로 정렬된 아이들은 이동시킬 필요가 없다. 나머지 아이들을 최장 증가 수열에 속해있는 아이들 사이에 넣어주면 되기 때문에 LIS 알고리즘을 통해 최장 증가 수열의 길이를 계산한 뒤, 전체 어린이 숫자에서 빼주면 정답이 된다.

아래의 코드는 O(nlogn)의 복잡도를 갖는 LIS 알고리즘을 구현했다.

코드

C++

'알고리즘 문제 풀이' 카테고리의 다른 글

[백준] 5557 1학년  (0) 2020.11.01
[백준] 1644 소수의 연속합  (0) 2020.10.23
[프로그래머스] 최고의 집합  (0) 2020.10.22
[프로그래머스] 섬 연결하기  (0) 2020.10.21
[백준] 1915 가장 큰 정사각형  (0) 2020.10.20
'알고리즘 문제 풀이' Related Articles more