[백준] 21317번 - 징검다리 건너기 (C++) 문제 및 풀이

문제) 백준 - 동적 계획법 - 징검다리 건너기

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

21317번: 징검다리 건너기

 

전형적인 동적 계획법으로 쉽게 해결할 수 있는 문제였습니다. solve(i, usedMegajump)를 통해 i 번째 돌까지 갔을때 필요한 최소 에너지의 memoization을 통해 해결합니다. 

 

C++ 소스코드)

	int solve(int idx, int usedMegaJump){
	if(idx == N) return 0;
	if(idx > N) return INF;
	int &ret = cache[idx][usedMegaJump];
	if(ret != -1) return ret;
	ret = INF;
	// Small Jump
	ret = min(ret, solve(idx + 1, usedMegaJump) + jumpEnergy[idx].first);
	// Big Jump
	ret = min(ret, solve(idx + 2, usedMegaJump) + jumpEnergy[idx].second);
	// Mega Jump
	if(usedMegaJump == 0)
	ret = min(ret, solve(idx + 3, 1) + K);
	return ret;
	}

view raw 21317.cpp hosted with ❤ by GitHub

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/21317_%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC%EA%B1%B4%EB%84%88%EA%B8%B0.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions