이동하기

문제

내가 푼 풀이 (탑다운)

문제에서 이동할 수 있는 범위는 3가지로
(r + 1, c)
(r, c + 1)
(r + 1, c + 1)이다.
이 3가지 경우에서 최대값을 구하는 DP형식으로 문제를 풀었지만 시간초과가 발생하였다.

내가 푼 풀이 (탑다운 - 최적화?)

처음 푼 풀이와 다를 것이 없다.
하지만 한 가지가 다른데 이동할 수 있는 범위가 다르다.
여기서는 이동할 수 있는 범위는 2가지로
(r + 1, c),
(r, c + 1)이다.
왜 (r + 1, c + 1)의 경우를 안해도 되냐면 (r + 1, c + 1)은 항상 (r + 1, c), (r, c + 1)을 경유해서 오기 때문이다.
이렇게 하면 시간초과 발생하지 않고 풀 수 있다.

다른 풀이(바텀업)