[BOJ/백준][Gold5] 17069 : 파이프 옮기기 2 (C++)

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

17069번: 파이프 옮기기 2

 

 

[난이도] Gold5
[유형] DP

[풀이]
DP[r][c][k] : 파이프의 끝이 r,c에 있고 모양이 k일때 (N,N)에 도착할 수 있는 경우의 수, (0:가로,1:세로,2:대각선)
현재 모양 k에 따라 dp 점화식을 세워주면 됩니다.

 

#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
int N,board[35][35];
ll dp[35][35][3];
ll sol(int r,int c,int k){
    if(r==N&&c==N) return 1;
    ll& ret = dp[r][c][k];
    if(ret!=-1) return ret;
    ret=0;
    if(k==0){
        if(!board[r][c+1]) {
            ret+=sol(r,c+1,0);
            if(!board[r+1][c+1] && !board[r+1][c]) ret+=sol(r+1,c+1,2);
        }
    }
    if(k==1){
        if(!board[r+1][c]) {
            ret+=sol(r+1,c,1);
            if(!board[r+1][c+1] && !board[r][c+1]) ret+=sol(r+1,c+1,2);
        }
    }
    if(k==2){
        if(!board[r][c+1]) ret+=sol(r,c+1,0);
        if(!board[r+1][c]) ret+=sol(r+1,c,1);
        if(!board[r+1][c+1] && !board[r+1][c] && !board[r][c+1]) ret+=sol(r+1,c+1,2);        
    }
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++) 
            scanf("%d",&board[i][j]);
    for(int i=1;i<=N+1;i++) board[N+1][i]=board[i][N+1]=1;
    memset(dp,-1,sizeof(dp));
    printf("%lld",sol(1,2,0));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/17069.cpp