목록2016/09/04 (1)
:: ADVANCE ::
[BaekJoon][2184] 김치 배달
BAEKJOON ONLINE JUDGE 2184 김치 배달 https://www.acmicpc.net/problem/2184 DPDP 테이블을 설정하기에 앞서문제를 잘 파악하면 배달을 하기위한 움직임이 왼쪽으로 이동, 오른쪽으로 이동 밖에 없으며,가는 길에 배달할 지역을 뛰어넘는 (예를 들어 10에서 출발, 9을 들리지 않고 1을 먼저 배달하는) 경우는 발생하지 않는다는 점을 알아야 한다.따라서 DP 테이블을 구간으로 잡을 수 있는데 먼저, DP[left][right] 에서 left - right 범위 내 위치한 배달할 지역은 이미 배달을 완료한 상태로 최적화가 될 수 있다.따라서 처음 공장 위치를 시작으로 범위를 점차 넓혀 나가는 식으로 탐색해 나간다. 또한 주의할 점이 하나 더 있다. 예를 들어 10..
Algorithm/DP (동적계획법)
2016. 9. 4. 03:46