[백준] 10653번 - 마라톤 2 (C++) 문제 및 풀이

문제) 백준 - 동적 계획법 - 마라톤 2

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

10653번: 마라톤 2

 

모든 체크 포인트의 좌표를 입력 받아 거리를 미리 계산합니다. 그 후, 체크 포인트를 뛰어넘는 경우와 그렇지 않는 경우로 각 최소 거리를 계산합니다.

 

C++ 소스코드)

	int solve(int idx, int ck) {
	if (idx == 0) return 0;
	int& ret = cache[idx][ck];
	if (ret != -1) return ret;
	ret = INF;
	for (int i = 0; i <= ck; ++i)
	if(idx - i - 1 >= 0)
	ret = min(ret, solve(idx - 1 - i, ck - i) + dist[idx -1 -i][idx]);
	return ret;
	}

view raw 10653.cpp hosted with ❤ by GitHub

 

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/10653_%EB%A7%88%EB%9D%BC%ED%86%A4%202.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions