BOJ 14585 - 사수빈탕

문제 링크

---

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

문제 해결

---

 1. (0, 0) 에서부터 x 좌표가 증가하는 방향과 y 좌표가 증가하는 방향으로만 이동한다. → Dynamic Programming으로 해결할 수 있음을 알 수 있는 부분.

주의할 점 || 생각해볼 점

---

 1. M의 값이 1,000,000이고 N의 값이 300이면 M*N = 3억이 될 수 있으므로 (int형 범위를 초과할 수 있으므로) 자료형은 long long을 선택한다.

 2. 매 시간마다 1씩 줄어드는 것을 따로 구현할 필요가 없이 가로와 세로의 값을 최초 사탕의 값에서 빼주면 된다. ( a[x][y] - (x+y) )

 3. 처음 문제를 봤을 때, BFS(넓이 우선 탐색)를 이용해서 문제를 해결하려 했다. 그러나 문제가 발생했다.

    (0, 0) 에서 (1, 3)으로 이동하는 과정에서 BFS를 이용하면 사탕 수가 최대 2가 아닌 1이 되어버린다. 방문했던 좌표를 체크하는 배열에 현재 사탕 바구니의 개수를 나타내는 인덱스를 추가한다해도 다를 바가 없다. 

    이번엔 아래 먼저 큐에 넣게 되면 7번에서 사탕 수는 같게 되나, 그 값이 다르게 된다. (처음 1에서 들어간 값이 더 큰데, 4의 값으로 덮어쓰게 된다.). M의 값이 1,000,000 이므로 M의 값으로 인덱스를 추가하기도 어렵다.

    그래서 포기하였다...  

 

참고

---

 - 

※ 정확하고 부드러운 태클은 언제나 환영입니다.