전깃줄 문제는 다이나믹 알고리즘의 LIS를 응용하는 문제이다.
입력받은 전봇대의 쌍 중에서 하나를 기준으로 정렬하여,
정렬되지 않은 전봇대중 가장 많이 정렬되어 있는 전봇대의 값에서 전체를 빼면
제거해야할 최소의 전봇대 개수가 된다.
반응형
'알고리즘 > 정올' 카테고리의 다른 글
[정올][bfs] 2613 토마토(고) (0) | 2017.05.12 |
---|---|
[정올][다이나믹] 1411 두 줄로 타일 깔기 (0) | 2017.04.25 |
[정올][분할정복] 1335 색종이만들기 (0) | 2017.04.14 |
[스크랩] [정올] 문제 해답 (0) | 2017.04.13 |
[정올][다이나믹] 1520 계단오르기 (0) | 2017.04.13 |