[백준 / C언어] 9184번: 신나는 함수 실행

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

9184번: 신나는 함수 실행

난이도: solved.ac 실버 2

 

알고리즘 분류

---

다이나믹 프로그래밍 (dp)

 

구현

---

배열의 index는 0부터 시작하므로 50을 더해 0부터 100까지의 index를 가진 3차원 배열 dp를 만들어주었다

문제에서 주어진 pseudo 코드를 그대로 옮기면 안된다

나는 두 번째 if문을 따로 처리해주었다

(이유: pseudo 코드의 순서대로 진행하면 w(20,20,20)이 만들어지지 않았는데 w(20,20,20)을 사용해야함)

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int dp[101][101][101];

int main() {
	int a, b, c;
	for (a = 0; a <= 100; a++) {
		for (b = 0; b <= 100; b++) {
			for (c = 0; c <= 100; c++) {
				if (a <= 50 || b <= 50 || c <= 50)
					dp[a][b][c] = 1;
				else if (a < b && b < c) 
					dp[a][b][c] = dp[a][b][c - 1] + dp[a][b - 1][c - 1] - dp[a][b - 1][c];
				else
					dp[a][b][c] = dp[a - 1][b][c] + dp[a - 1][b - 1][c] + dp[a - 1][b][c - 1] - dp[a - 1][b - 1][c - 1];
			}
		}
	}
	for (a = 51; a <= 100; a++) {
		for (b = 51; b <= 100; b++) {
			for (c = 51; c <= 100; c++) {
				if (a > 70 || b > 70 || c > 70)
					dp[a][b][c] = dp[70][70][70];
			}
		}
	}
	while (1) {
		scanf("%d %d %d", &a, &b, &c);
		if (a == -1 && b == -1 && c == -1)
			break;
		else
			printf("w(%d, %d, %d) = %d\n", a, b, c, dp[a + 50][b + 50][c + 50]);
	}
	return 0;
}