[백준] 14863번 - 서울에서 경산까지 (C++) 문제 및 풀이

문제) 백준 - 동적 계획법 - 서울에서 경산까지

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

14863번: 서울에서 경산까지

 

도보로 이동하거나 자전거를 이용하는 방법을 택하여 제한 시간 이내에 얻을 수 있는 최대 모금액을 구하는 문제였습니다. 동적 계획법을 통해 해당 구간과 제한 시간을 memoization 하여 해결합니다.

 

C++ 소스코드)

	int cache[MAX][100001];
	int solve(int now, int t){
	if(t > K) return -INF;
	if(now == N + 1) return 0;
	int &ret = cache[now][t];
	if(ret != -1) return ret;
	ret = solve(now + 1, t + walk[now].first) + walk[now].second;
	if(t + bycicle[now].first <= K)
	ret = max(ret, solve(now + 1, t + bycicle[now].first) + bycicle[now].second);
	return ret;
	}

view raw 14863.cpp hosted with ❤ by GitHub

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/14863_%EC%84%9C%EC%9A%B8%EC%97%90%EC%84%9C%EA%B2%BD%EC%82%B0%EA%B9%8C%EC%A7%80.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions