문제

문제 링크

해설

• 문제에서 알고리즘의 psuedo code가 주어지므로 그대로 재귀호출 함수를 구현하면 됩니다.
• 다만, a, b, c 셋 중 하나라도 0을 포함한 음수일 경우, 20을 초과한 자연수일 경우에 특수한 조건이 있습니다.
• 입력조건을 보면 세 변수의 범위는 -50 부터 50까지라는 점을 주의합시다.
• 그리고, 계속해서 같은 값이 계산되므로 DP[21][21][21] 3차원 배열을 활용해서 메모이제이션을 하면, 이미 계산한 값에 대해서는 재귀호출을 생략할 수 있습니다.

코드

#include <bits/stdc++.h>
using namespace std;

int DP[21][21][21];

int go(int a, int b, int c) {
	if (a <= 0 || b <= 0 || c <= 0) return 1;
	if (a > 20 || b > 20 || c > 20) return go(20, 20, 20);
	if (DP[a][b][c]) return DP[a][b][c];
	return DP[a][b][c] = (a < b && b < c) ? 
		(go(a, b, c - 1) + go(a, b - 1, c - 1) - go(a, b - 1, c)) :
		(go(a - 1, b, c) + go(a - 1, b - 1, c) + go(a - 1, b, c - 1) - go(a - 1, b - 1, c - 1));
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int a, b, c;
	while (true) {
		cin >> a >> b >> c;
		if (a == -1 && b == -1 && c == -1) break;
		cout << "w(" << a << ", " << b << ", " << c << ") = " << go(a, b, c) << "\n";
	}
}

결과