[SWEA] 9092. 마라톤
이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다.
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW7Opy-KWPoDFAWY&
DP와 찰떡궁합인 문제.
DP를 적용하면 너무나 예쁘게 풀립니다.
http://colorscripter.com/s/SqvPRIB
https://github.com/rundun159/PS/blob/master/Problem_Solving/9092.cpp
(제가 구현한 코드입니다.)
제 코드에서 핵심이 되는 matrix는 graph와 cache입니다.
먼저, graph라는 2D array에 각 지점들 사이의 L1거리를 저장합니다.
(연산횟수를 줄이기 위함입니다. 매번 계산하면 연산 횟수가 늘어나겠죠.)
각 지점에서 모든 지점까지의 거리는 구할 필요가 없고,
해당 지점에서 k+1개의 지점들까지의 거리만 구하면 됩니다.
(점프를 안하는 경우까지 포함해서, 최대 k번 점프해서 이동할 수 있는 지점의 개수 : k+1)
그 다음,
cache 2D array에 해당 지점(state.p)에서 최대 k(state.q)만큼 점프해서
결승점에 도달 할 수 있는 최소 거리를 저장합니다.
해당 state에서 최소 거리는
(state.p에서 i번째 지점까지의 거리 + i번째 지점에서 결승점까지의 최소 거리) 로 구할 수 있습니다.
(점화식의 형태이므로 DP를 적용할 수 있습니다.)
점프하는 것을 고려해서 state를 갱신해야합니다.
어느 피드백이든 환영합니다!