백준 11048

[11048] 이동하기

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net 🔎 해결 방법 (1, 1)에서부터 (n, m)까지 가면서 오른쪽, 대각선, 아래쪽 중 가장 큰 값을 더해나가면 되지 않을까? 그럼 dp가 필요없는데? 라고 생각했지만 이 문제를 dp로 풀어야 하는 이유가 있다. 만약의 미로가 위와 같이 주어졌다면, 현재 내 위치에서 갈 수 있는 칸 중 가장 최댓값만 취해서 이동한다면 위와 같이 되고, 이것은 dp가 아니라 그리디 알고리즘이라고 ..