우유 도시

23 Oct 2018

Problem

https://www.acmicpc.net/problem/14722

Idea

초코우유부터 마실 수 있으므로 뒤에서부터 생각하기보다 앞에서 생각이 편한 것 같다.

memo[x][y][k] = 현재 k 우유를 마실 차례일 때 x,y 에서 부터 마실 수 있는 최대 수

각 상태에서 k 우유를 마실 수도, 안마실 수도 있다.

memo[x][y][k] = max(
        f(x+1, y, k),
        f(x, y+1, k),
        f(x+1, y, k next) + 1,
        f(x, y+1, k next) + 1
) if (k == map[x][y])

memo[x][y][k] = max(
        f(x+1, y, k),
        f(x, y+1, k),
} if (k != map[x][y])

Problem

Idea

Related