백준 17069 파이프 옮기기 2 C++

 

간단한 해설

 

단순히 메모이제이션을 통해서 파이프를 옮기면 된다.

 

파이프의 모양이 3개 있으니까, 2차원 위치를 나타내는 배열 + 파이프의 모양으로 3차원 배열 선언하였다.

 

 

그런데 자꾸 예제 5번의 답이 50445956이 나와서, 다른 예제는 다 맞는데 뭐가 문제이지 1시간고민했었는데,

정답인 4345413252가 43억으로 int 형의 범위를 초과해서 그런 것이였다. 감이 다죽었네...

 

 

답

 

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    vector<vector<ll>> v(n,vector<ll>(n));
    vector<vector<vector<ll>>> dp(n+1,vector<vector<ll>>(n+1,vector<ll>(3,0)));
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            cin>>v[i][j];
        }
    }
    dp[0][1][0]=1;
    for(int i=2;i<n;++i){
        if(v[0][i]==0){
            dp[0][i][0]=1;
        }
        else break;
    }
    for(int i=1;i<n;++i){
        for(int j=1;j<n;++j){
            if(v[i][j]==0){
                dp[i][j][0]+=dp[i][j-1][0]+dp[i][j-1][1];
                dp[i][j][2]+=dp[i-1][j][2]+dp[i-1][j][1];
                if(v[i-1][j]==0&&v[i][j-1]==0){
                    dp[i][j][1]+=dp[i-1][j-1][0]+dp[i-1][j-1][1]+dp[i-1][j-1][2];
                }
            }
        }
    }
    ll ans=dp[n-1][n-1][0]+dp[n-1][n-1][1]+dp[n-1][n-1][2];
    cout<<ans;
}