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

생각의 흐름

문제 이해가 안돼서 그냥 무작정 w(1, 1, 1), w(2, 2, 2)를 써봤다. 이 값을 문제에 나와있는 함수에 대입하니 식이 엄청 많이 나왔다. 동적 계획법에 맞게 중복되는 값을 피보나치처럼 지우면 되겠구나 싶었다.

• 일단 예외처리해야 할 케이스를 정했다.

1. a b c 셋중 하나라도 0이거나 0보다 작을경우

2. a b c 셋중 하나라도 20보다 클 경우

3. a < b < c 일 경우

4. 출력은 무한루프를 돌리고, -1 -1 -1입력받으면 탈출시키도록

• 그다음에 우리는 동적 계획법을 사용할 것이다. 그러려면 값을 미리 다 정해놓고, a b c입력받으면 그걸 바로 출력시키면 된다.

• 값을 미리 정해놔야되는데, 그 저장할 공간이 필요하다. 3차원배열을 떠올렸다.

• 그 3차원 배열에 값을 정하는 방법을 정해야된다. 반복문으로 밑에서부터 쌓냐(bottom-up) 재귀로 위에서부터 내려오냐(top-down)를 정할건데, 나는 재귀 잘 못해서 반복문으로 진행했다.
  근데 생각해보니 재귀로 할걸 그랬다 재귀를 써봐야 재귀 실력이 늘텐데..

• 이정도만 정해놓고, 코드를 짰다.

내가 푼 코드

#include <stdio.h>

int main()
{
	int i, j, k;
	int arr[21][21][21];
	i = 0;
	while (i <= 20)
	{
		j = 0;
		while (j <= 20)
		{
			k = 0;
			while (k <= 20)
			{
				if (i == 0 || j == 0 || k == 0)
				{
					arr[i][j][k] = 1;
				}
				else if (i < j && j < k)
				{
					arr[i][j][k] = arr[i][j][k - 1] + arr[i][j - 1][k - 1] - arr[i][j - 1][k];
				}
				else
				{
					arr[i][j][k] = arr[i - 1][j][k] + arr[i - 1][j - 1][k] + arr[i - 1][j][k - 1] - arr[i - 1][j - 1][k - 1];
				}
				k++;
			}
			j++;
		}
		i++; // 밑에서부터 차곡차곡 쌓아올라갔다.
	}
	while (1) // 출력할때 필요함.
	{
		scanf("%d %d %d", &i, &j, &k);
		if (i == -1 && j == -1 && k == -1)
			break;
		else if (i <= 0 || j <= 0 || k <= 0)
			printf("w(%d, %d, %d) = 1\n", i, j, k);
		else if (i > 20 || j > 20 || k > 20)
			printf("w(%d, %d, %d) = %d\n", i, j, k, arr[20][20][20]);
		else 
			printf("w(%d, %d, %d) = %d\n", i, j, k, arr[i][j][k]);
	} // 문제에서 나온대로 예외도 순서대로 처리해주었다.
}

다른 사람 코드

https://chosh95.tistory.com/376

#include <iostream>
using namespace std;
int a, b, c;
int dp[51][51][51];

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

int main()
{
	while (true)
	{
		cin >> 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));
	}
}

c++이라 잘 모르는 부분이 있지만, 논리만 가져가자.
보면 w재귀를 돌린다.

문제 자체는 문제에서 주어진 순서대로 구현하면 된다.
w(a, b, c)를 dp에 넣어서 dp[a][b][c]가 이미 있는 값이면 반환해야 한다.
여기서 a나 b, c 중 하나라도 0이하의 수가 있으면 index관련한 오류가 뜰 것이다.
따라서 w함수에서 a,b,c중 음수가 있는지 먼저 판별한 후에 dp를 읽는다.
그것만 주의하면 어려울점은 없을 것 같다.