bottom-up과 top-down 형식의 DP(백준 14238)

백준 14238번을 풀면서 깨달은 점에 대해 정리.

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

 

보통 DP를 쓸 때에는 dfs 재귀함수와 조합하는 편이고,

그리고 (나의 경우에만 국한되는지는 모르나) dfs 재귀는 보통 top-down 방식을 단순하게 짜기 위해 사용한다.

아주 대표적인 예로 피보나치 수열을 dfs로 구현할 때의 dp 사용이 여기에 해당하겠다.

그런데 꼭 재귀방식의 dfs가 top-down으로만 사용되지는 않고 bottom-top 방식으로도 충분히 사용 가능하다

백준 14238번 문제의 경우 bottom-top으로 구현할때 dp가 해야하는 역할은 아래와 같다

 

그냥 개념적으로는 당연히 반대로 적용하면 되는데 코드 적용 시 직관적으로 이해가 가지 않았던 부분이었는데

이게 이제야 이해가 간 기분이어서 정리해봤다

 

같이 첨부해보는 내 답안 코드

//https://www.acmicpc.net/problem/14238
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int dp[51][51][51][3][3]; //[a개수][b개수][c개수][전전날일한사람][전날일한사람] 일 경우 차후 조합으로 가능한지 저장,  초기화 -1
string s;
string answer;
int maximum[3]; //abc 한도

bool go(int a, int b, int c, int before2day, int before1day)
{
    int &ans = dp[a][b][c][before2day][before1day];
    if(a+b+c == s.size())//탈출 조건
    {
        return ans = true;
    }
    if(ans != -1)
    {
        return ans;
    }

    //A - 유효성검사 필요 X
    if(a < maximum[0] && go(a+1,b,c,before1day,0))
    {
        answer = 'A' + answer;
        return ans = true;
    }
    //B
    if(b < maximum[1] && before1day != 1 && go(a,b+1,c,before1day,1))
    {
        answer = 'B' + answer;
        return ans = true;
    }
    //C
    if(c < maximum[2] && before1day != 2 && before2day != 2 && go(a,b,c+1,before1day,2))
    {
        answer = 'C' + answer;
        return ans = true;
    }

    return ans = false;
}

int main()
{
    cin >> s;
    for(auto a : s)
    {
        maximum[a-'A']++;
    }
    memset(dp, -1, sizeof(dp));


    if(go(0,0,0,0,0))//어차피 A는 조건에 안걸리므로 일한사람이 없어도 0으로 통일함
    {
        cout << answer;
    }
    else
    {
        cout << -1;
    }

}