BOJ 17070 파이프 옮기기 1

문제 링크 : https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

파이프가 점거하는 두 점 중에서 목적지에 가까운 점(행 또는 열의 좌표가 큰점)을 기준으로 dp 를 구성한다.

dp[i][j][0] 은 가로, dp[i][j][1] 은 세로 그리고 dp[i][j][2] 는 대각선으로 놓인 상태이다.

 

전이는 0 이 되려면, 즉 가로로 놓을 수 있으려면 원래 0 (가로), 2(대각선) 상태에서 가능하다.

\[ dp[i][j+1][0]=dp[i][j][0]+dp[i][j][2] \]

다른 것들도 대동소이하다. (장애물 체크만 해주면)

 

#include<bits/stdc++.h>

using namespace std;

int grid[17][17],dp[17][17][3];

int main(){
    int n; scanf("%d",&n);
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&grid[i][j]);
    
    dp[1][2][0]=1;   
    
    for(int i=1;i<=n;i++){
        for(int j=2;j<=n;j++){
            if(j+1<=n && grid[i][j+1]==0)
                dp[i][j+1][0]=dp[i][j][0]+dp[i][j][2];
            if(i+1<=n && grid[i+1][j]==0)
                dp[i+1][j][1]=dp[i][j][1]+dp[i][j][2];
            if(i+1<=n && j+1<=n && 
               !grid[i+1][j] && !grid[i][j+1] && !grid[i+1][j+1])
                dp[i+1][j+1][2]=dp[i][j][0]+dp[i][j][1]+dp[i][j][2];
        }
    }
    printf("%d\n",dp[n][n][0]+dp[n][n][1]+dp[n][n][2]);
}