마라톤 2 (10653번) - 백준 (BOJ)

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

10653번: 마라톤 2

 

 

백준 - 마라톤 2 (Marathon) (10653번)

 

난이도 : Gold 3

알고리즘&자료구조 : Dynamic Programming (동적계획법)

---

★ 핵심 Idea ★

 

◎ 젖소가 X번 체크포인트까지 이동했을 때,

0 ~ K 번 건너뛴 경우 각각에 대해서 최솟값을 기록한다.

 

위 작업을 1번부터 N번 체크포인트까지 순차적으로 진행하면,

마지막 N번 체크포인트에서의 최솟값이, 문제에서 요구하는 최소거리가 된다.

 

 

< 전체 코드 >

 

import sys
input = sys.stdin.readline


class Marathon():
    def __init__(self, N, K):
        self.points = [tuple(map(int, input().split())) for _ in range(N)]
        table = [[sys.maxsize] * (K+1) for _ in range(N)]
        table[0][0] = 0
        for cur in range(1, N):
            for k in range(min(cur, K+1)):
                table[cur][k] = min(table[cur-kk-1][k-kk] + self._get_dist(cur-kk-1, cur) for kk in range(k+1))
        self.miny = min(table[-1])


    def _get_dist(self, i, j):
        return abs(self.points[i][0] - self.points[j][0]) + abs(self.points[i][1] - self.points[j][1])


if __name__ == '__main__':
    course = Marathon(*map(int, input().split()))
    print(course.miny)