[백준] 14728번 - 벼락치기 (C++) 문제 및 풀이

문제) 백준 - DP(동적 계획법) - 벼락치기

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

14728번: 벼락치기

 

한정된 시간에 최대 점수를 내기 위해 선택해야하는 전형적인 냅색(배낭) 문제. 

DP(인덱스, 남은 공부 시간)으로 해결할 수 있다.

 

 

C++ 소스코드)

	int solve(int idx, int T) {
	if (idx == N) return 0;
	int& ret = cache[idx][T];
	if (ret != -1)return ret;
	// PASS
	ret = solve(idx + 1, T);
	// Study
	if (T >= StudyTime[idx])
	ret = max(ret, solve(idx + 1, T - StudyTime[idx]) + Score[idx]);
	return ret;
	}

view raw 14728.cpp hosted with ❤ by GitHub

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/14728_%EB%B2%BC%EB%9D%BD%EC%B9%98%EA%B8%B0.cpp

GitHub - Chocochip101/BOJ_Solution