2017. 7. 30. 10:50ㆍ알고리즘 문풀/BOJ 연습
2969. 메뚜기 (COCI 08/09 Contest #1 5번)
문제 : http://icpc.me/2969
오래전에 친구가 교내 대회에 냈던 문제인데, 그때 아무생각없이 \(O(n^4)\)이랑 \(O(n^3)\) 생각하고 끝냈던 문제.
일단 \(dp[i][j]\)를 \((i,j)\)에서의 최장 경로라고 하자. 이제 각각 \(n\)개씩의 행/열에 대해서 \(dp\)값과 좌표를 저장해두는 자료구조를 만든다.
높이가 낮아지는 순서대로 탐색하면서, i+1열, i-1열, j-1열, j+1열에 저장된 dp값들 중 조건을 만족하면서 가장 큰 dp값을 \(D\)라고 하면, \(dp[i][j]=D+1\)이 된다.
자료구조를 맨 처음에는 set으로 했는데, set을 허투루 썼더니 메모리 초과가 났다(...) 여윽시 set/map은 사회악 (heap으로 했으면 AC가 났을지도?)
여기서 시간을 줄일 수 있는 아이디어는 한 행/열에서 dp값이 가장 큰 4개의 값만 들고 다니면, 그 4개 중에 문제의 까다로운 좌표 조건을 만족하는 놈이 반드시 존재한다는 것이다. 그래서 자료구조는 그냥 한 열당 4개짜리 배열로 충분하다.
여기서 한 가지 신경써줘야 할 점은 높이가 같은 점은 한 열에 최대 \(n\)개까지 존재할 수 있으므로, 이걸 고려하지 않고 바로 자료구조에 현재 dp값을 삽입하면 WA를 받게 된다. 높이가 같은 점들끼리는 따로 \(tmp\)같은 벡터에 저장해 두었다가 높이가 달라지는 순간 \(tmp\)를 비우면서 자료구조에 넣어주어야 한다.
Time Complexity : \(O(\text{sort}(n^2)+n^2) = O(n^2 \lg n)\)
'알고리즘 문풀 > BOJ 연습' 카테고리의 다른 글
| 8/1 연습 (0) | 2017.08.02 |
|---|---|
| 7/30 ~ 7/31 연습 (0) | 2017.08.01 |
| 7/27~7/28 연습 (0) | 2017.07.29 |
| 7/26 연습 (0) | 2017.07.27 |
| 7/25 연습 (0) | 2017.07.26 |