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

www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

바본가...출력 형식을 무시해서 이유없이 코드를 고쳤다....

 

문제에서도 나와있지만: 재귀함수로는 어렵지 않지만 시간 초과가 발생하는 문제이다.

그럼 당연 dp지

 

라고 생각했지만 확신은 없었다 ㅋㅋㅋㅋㅋㅋ 3차원 배열..?진짜..? 진짜였다.

 

주어진 조건대로

1. 셋 중 하나라도 0이하

-> return 1

2. 셋 중 하나라도 20이상

-> w(20, 20, 20) 호출

3. a<b<c

어떤 식

4. 그 외

어떤 식

 

이런 구조다.

 

그렇다묜 1번 2번을 진행해서 a,b,c를 적절하게 변환하고

dp[a][b][c]값이 있다면 그 값을 리턴

아직 없다면 값을 찾으러 재귀 실행! 이 되어야 할 것이다.

그래서 코드가 요렇다

 

#include <stdio.h>

using namespace std;
int dp[21][21][21];
int a, b, c;

int ref(int a, int b, int c)
{

  if (a <= 0 || b <= 0 || c <= 0)
  {
    return dp[0][0][0] = 1;
  }

  if (a > 20 || b > 20 || c > 20)
  {
    return ref(20, 20, 20);
  }

  if (dp[a][b][c] != 0)
  {
    return dp[a][b][c];
  }

  if (a < b && b < c)
  {
    return dp[a][b][c] = ref(a, b, c - 1) + ref(a, b - 1, c - 1) - ref(a, b - 1, c);
  }
  else
  {
    return dp[a][b][c] = ref(a - 1, b, c) + ref(a - 1, b - 1, c) + ref(a - 1, b, c - 1) - ref(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;
    }
    int res = ref(a, b, c);
    printf("w(%d, %d, %d) = %d\n", a, b, c, res);
  }
  return 0;
}