블로그 이사 중입니다 >> gumgood.github.io

1520 내리막 길 본문

Problem Solving/문제 풀이

1520 내리막 길

gumgood 2018. 2. 5. 08:58

C++11


1차원 DP로 해결



dp[i][j] = i,j에 도달 할 수 있는 모든 경우의 수


초기화 : dp[0][0] = 1, 나머지 0


각 좌표 (i, j)를 해당하는 지점의 높이를 기준으로 내림차순으로 정렬


가장 높은 지점에서 내려가면서, 각 지점의 이웃(상하좌우) 중에 도달할 수 있는 지점에 dp값을 넘겨준다.


2차원 배열이지만 각 지점을 한번식 방문한다.


이 과정은 전체 지점의 갯수 N(=nm)에 대해 O(N)이다.


이웃지점의 dp배열에서의 인덱스를 알아내는데 이분탐색을 이용했다. O(logN)


따라서 전체 시간복잡도는 O(NlogN)



* DFS로 푼 사람들도 있음

'Problem Solving > 문제 풀이' 카테고리의 다른 글

11651 좌표 정렬하기 2  (0) 2018.02.05
11724 연결 요소의 개수  (0) 2018.02.05
1520 내리막 길  (0) 2018.02.05
8595 히든 넘버  (0) 2017.06.13
10571 다이아몬드  (0) 2017.06.13
2447 별찍기 - 10  (0) 2017.06.12
Tag
,
0 Comments
댓글쓰기 폼