7/29 연습

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/29 연습  (0) 2017.07.30
7/27~7/28 연습  (0) 2017.07.29
7/26 연습  (0) 2017.07.27
7/25 연습  (0) 2017.07.26