[백준] 15990번 - 1, 2, 3 더하기 5 (C++) 문제 및 풀이

문제) 백준 - DP(동적 계획법) - 1, 2, 3 더하기 5

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

15990번: 1, 2, 3 더하기 5

 

이전 사용한 숫자(prev)를 memoization하여 prev를 제외한 숫자를 사용하여 합을 나타낼 수 있는 방법을 계산한다.

 

C++ 소스코드)

 

	int solve(int k, int prev) {
	if (k == 0) return 1;
	int& ret = cache[k][prev];
	if (ret != -1) return ret;
	ret = 0;
	if (prev != 1 && k >= 1)
	ret += solve(k - 1, 1) % MOD;
	if (prev != 2 && k >= 2)
	ret += solve(k - 2, 2) % MOD;
	if (prev != 3 && k >= 3)
	ret += solve(k - 3, 3) % MOD;
	return ret % MOD;
	}

view raw 15990.cpp hosted with ❤ by GitHub

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2015000~19999/15990_1%2C%202%2C%203%20%EB%8D%94%ED%95%98%EA%B8%B0%205.cpp

GitHub - Chocochip101/BOJ_Solution