사수빈탕
-
백준 14585번 사수빈탕 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 5. 30. 23:38
이번 글은 백준 알고리즘 문제 14585번 "사수빈탕" 을 다뤄본다.문제는 2017 고려대학교 프로그래밍 대회에서 출제된 문제이다.문제 풀이는 동적계획법으로 접근할 수 있다. 수빈이는 좌표평면 위에 앉아있다. "나는 좌표평면이 너무 좋아!!" 라고 수빈이가 말했다. 좌표평면에는 N개의 사탕바구니가 있고, 각 사탕 바구니에는 M개의 사탕이 있다. 각 사탕 바구니는 (x1, y1), (x2, y2), …, (xn, yn)에 있고, 수빈이는 (0, 0)에 있다.오늘은 날씨가 덥다. 따라서 시간이 1만큼 지날 때마다 모든 사탕바구니에서 사탕은 1만큼 줄어든다. 수빈이는 매우 배가 고프기 때문에, 사탕바구니에 있는 사탕을 순식간에 모두 먹을 수 있다. 수빈이가 1만큼 움직일 때, 시간은 1만큼 지나간다. 수빈이는..