[백준 9184번] 신나는 함수 실행

문제 링크: N번 제목

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

 

어떤 점에서 동적 계획법 문제라고 생각할 수 있을까요?

 

복잡하게 생각할 것 없이, a > 20 or b > 20 or c > 20인 케이스만 해도 w(20, 20, 20)를 호출하며, 이는 4번 케이스에 해당하는데 각각 w를 4번 호출하므로 값을 기억하는 편이 편합니다.

한편, a, b, c가 증가할 수록 w() 호출값이 커지는 형태인데 w(50, 50, 50)의 반환값이 예제에서 정의되어 있으므로 int 범위를 넘을 걱정은 하지 않아도 됩니다.

 

#include <stdio.h>

int a, b, c, d[51][51][51];

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

int main(void) {
	while (1) {
		scanf("%d %d %d", &a, &b, &c); if (a == -1 && b == -1 && c == -1) break;
		printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
	}
	return 0;
}