[백준] 4811번 - 알약 (C++) 문제 및 풀이

문제) 백준 - 동적 계획법(Dynamic Programming) - 알약

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

4811번: 알약

 

cache[w][h]: 약 w(한 조각), h(반 조각)의 개수 memoization

solve(w, h): top-down방식으로 알약 한 조각 먹을수 있는 경우(w > 0), 반 조각 먹을 수 있는 경우(h > 0)를 더해서 return

 

 

C++ 소스코드)

	int cache[MAX][MAX];
	int solve(int w, int h) {
	//기저 사례
	if (w == 0) return 1;
	int& ret = cache[w][h];
	if (ret != -1) return ret;
	ret = 0;
	if (w > 0)
	ret += solve(w - 1, h + 1);
	if (h > 0)
	ret += solve(w, h - 1);
	return ret;
	}

view raw 4811.cpp hosted with ❤ by GitHub

 

Full code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/4811_%EC%95%8C%EC%95%BD.cpp

GitHub - Chocochip101/BOJ_Solution