BOJ 2411 아이템 먹기

N*M모양 맵에 아이템과 장애물이 있고, 맨 왼쪽 아래에서 출발해서 아이템을 모두 먹고 맨 오른쪽 위에 도착하는 경로의 수를 구하는 문제이다.
장애물은 지나갈 수 없고, 이동할 때는 오른쪽이나 위쪽으로 밖에 이동하지 못한다.

d[r][c][k] = (1, 1)에서 시작해서 (r, c)까지 아이템 k개를 먹으며 가는 경로의 수
로 놓으면 될 것 같은데... 아이템이 최대 10000개까지 있을 수 있는데... 오른쪽이나 위쪽으로 밖에 이동하지 못하니까 아이템은 최대 N+M-1개까지만 먹을 수 있다.
그렇기 때문에 d[r][c][k]의 배열 크기는 d[100][100][10000]이 아니라 d[100][100][200]으로 하면 될 것이다.

또 하나 생각나는 점이 주어지는 아이템이 정상적으로 이동하면서 다 먹을 수 있게 주어졌다면 아이템 방문 순서는 정해져 있다는 것이다. 오른쪽이나 위쪽으로만 이동하니까 아이템은 행, 열이 둘다 작거나 같은 것부터 이동해야 한다. 예를 들어 아이템이 (r1, c1), (r2, c2)가 있고, r1<=r2, c1<=c2이면 (r1, c1)부터 방문해야 한다. 아직 이것을 어떻게 적용시켜야 할지는 모르겠어서 일단 위에서 생각한대로 풀어 봐야겠다.

AC를 받았다. 근데 메모리와 실행 시간이 꽤 큰 편이다.

그래서 다른 분들 코드를 좀 봤더니 다들 d[r][c]로만 하신 것 같다. 내가 아까 처음에 생각했던 아이템의 방문 순서나 경로는 행, 열이 둘다 작거나 같은 것부터 먹으면서 가는 것이 맞다. 그래서 좀 더 생각을 해서 다시 코드를 짰다.
d[r][c] = (r, c)에서 시작해서 (n, m)까지 아이템을 모두 먹으며 가는 경로의 수
로 놓고, item의 좌표를 sorting해서 작은 것을 기준으로 길을 탐색한다. 위나, 오른쪽으로만 가야하므로 첫번째 아이템을 방문하기 전에 첫번째의 좌표보다 더 큰 좌표로 이동하면 안된다! 그래서 첫번째 아이템보다 더 행과 열이 작은 좌표로만 이동하는 경우만 허용하고, 만약 첫번째 아이템의 좌표에 도착하면 parameter로 보낸 아이템의 index를 index++해서 다음 아이템을 기준으로 또 길을 찾는다 . 그리고 마지막 n, m까지 도달하게 하기위해 item을 sorting한 후 item[a].r과 item[a].c에 n과 m을 넣어놨다.

이렇게 하면 자연스레 모든 아이템을 먹으면서 이동하게 되고 모든 아이템을 먹을 수 있는 경로만 이동하게 된다. 즉 무의미한 경로로 전혀 가지 않게되어 시간도 더 줄어드는 것 같다.
그래서 결국 AC를 받았다. 처음엔 그냥 다음에 할까 생각하면서 미루려고(피하려고) 했는데, 막상 해보니 할 만하고 메모리와 시간을 둘 다 줄여서 기분이 좋다.