혼종 꼬지마루
[백준] 1520 - 내리막길 본문
dp를 처음 시작하면서 이 문제를 꼭 풀어보면 좋다고 생각하는 문제
dfs로 검사하며 return하는 과정에서 메모이제이션을 해주는 문제로 필수문제라고 생각
1. 맵정보를 입력받으며 dp를 -1로 초기화
2. dfs로 내리막길을 찾으며 탐색
그 위치에서의 dp는 방문한 것을 체크하기 위해 0으로 만든다.
3. 도착점에 도착하면 1을 반환한다.
4. 만약 방문한 점이고, dp가 -1이 아니라면 그 지점의 값을 반환한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include <iostream> #define MX 503 using namespace std; int map[MX][MX], dp[MX][MX]; int dx[] = { 0, 0, -1, 1 }; int dy[] = { -1, 1, 0, 0 }; int N, M; int dfs(int x, int y) { if (x == M - 1 && y == N - 1) return 1; if (dp[y][x] > -1) return dp[y][x]; dp[y][x] = 0; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 0 || nx >= M || ny < 0 || ny >= N || map[ny][nx] >= map[y][x]) continue; dp[y][x] += dfs(nx, ny); } return dp[y][x]; } int main(void) { cin >> N >> M; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { cin >> map[i][j]; dp[i][j] = -1; } cout << dfs(0, 0) << "\n"; return 0; } | cs |
'Algorithms > DP' 카테고리의 다른 글
[백준] 4095 - 최대 정사각형 (0) | 2019.05.05 |
---|---|
[백준] 15559 - 내 선물을 받아줘 (0) | 2019.04.13 |
[백준] 9465 - 스티커 (0) | 2018.09.08 |
[백준] 11048 - 이동하기 (0) | 2018.08.29 |
[백준] 15486 - 퇴사2 (7) | 2018.08.27 |