[C++] 백준9184: 신나는 함수 실행(배열 초기화 하기,동적계획법)

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


1. 동적계획법이라고 해서 무조건 재귀 호출이 없는것은 아니다 

처음에 DP를 한차원의 크기가 101 인 배열로 만드려고 하다가 실패하였다.
한 차원의 크기가 21이여도 충분하다,
간단하게 처리할 수 있는 부분(a,b,c중 하나라도 0이하이거나 , 20이상일때)은 함수 재귀 호출을 하고 
시간처리가 중요한 구간은 DP의 데이터를 리턴하도록 해서 시간단축을 한다

 

2. vector 의 초기화와 달리 Array의 초기화는 main 함수내에서 fill 함수를 사용해서 해야한다.

 

fill(초기화할 주소값의 시작 , 초기화할 주소값의 끝 , 초기화할 값)

DP의 시작주소에서 DP의 size를 int의 size로 나눈것만큼이 이동하면 그게 끝 주소이다.

#include <iostream>
#include <algorithm>

using namespace std;


// 3차원 배열 DP 선언
int DP[21][21][21];


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

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


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

    // 여기가 핵심
    else if (DP[a][b][c] != -1) {
        return DP[a][b][c];
    }
    // 재귀가 발생하지 않게 해야 한다

    else if (a < b && b < c) {
        DP[a][b][c] = w(a,b,c - 1) + w(a,b - 1,c - 1) - w(a,b - 1,c);
        return DP[a][b][c];
    }

    else {
        DP[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);
        return DP[a][b][c];
    }
 
}


int main() {
    // 입력
    int A = 0;
    int B = 0; 
    int C = 0;

    // 3차원 배열을 0이 아닌 -1로 한번 초기화 해보고싶었다
    fill(&DP[0][0][0], &DP[0][0][0] + sizeof(DP) / sizeof(int), -1);
    
    while (true) {
        cin >> A >> B >> C;
        if (A == -1 && B == -1 && C == -1) {
            break;
        }
        cout << "w(" << A << ", " << B << ", " << C << ")" << " = " << w(A,B,C)<< "\n";
    }
    
}