[C++] 백준 17070: 파이프 옮기기 1

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

 

dp배열의 값 설정

문제에서 (N,N)로 이동시키는 방법의 개수를 물어봤으므로, 

dp[i][j] = (i, j)까지 이동시키는 방법의 개수라고 가정하고 시작했다.

 

이 문제는 좌표뿐만 아니라 방향값도 존재하므로 배열의 차원을 하나 늘려

방향값도 저장하는 게 좋겠다는 생각이 들었다.

 

그래서 dp[i][j][k] = k의 방향을 가지는 (i,j)까지 이동시키는 방법의 개수로 가정했다.

 

 

 

처음에 파이프는 가로 방향으로 (1,2)에 끝이 위치하므로

    dp[1][2][0] = 1;

 다음과 같이 초기값을 설정했고,

그 후에 점화식을 생각해보았다.

 

 

 

점화식 구하기

dp[n][n][0] = 가로 방향으로 (n,n)까지 이동시키는 방법의 개수이다.

 

즉, (n,n-1)에서 가로 방향(0)으로 (n,n)까지 이동시킨다는 뜻이고,

그럼 (n,n-1)에서의 끝이 가로 방향(0) 혹은 대각선 방향(1)의 방향을 가져야만 가로 방향을 값을 가질 수 있다.

이걸 식으로 표현하면

dp[n][n][0] = dp[n][n-1][0] + dp[n][n-1][1]이다.

 

 

그럼 이번엔 대각선 방향(1)을 보자.

대각선 방향은 이전 방향이 가로, 대각선, 세로 모두 가능하므로,

dp[n][n][1] = dp[n-1][n-1][0] + dp[n-1][n-1][1] + dp[n-1][n-1][2]이 된다!

 

 

마지막으로 세로 방향(2)을 보자.

세로 방향은 이전 방향이 대각선 또는 세로여야 가능한 방향이므로,

dp[n][n][2] = dp[n-1][n][1] + dp[n-1][n][2]이 되는 것이다!

 

 

이때 반복문의 조건을 간편하게 설정하며 초깃값을 이용하기 위해 =(대입 연산자)가 아닌 +=(복합 대입 연산자)를 활용하였다.

for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
                dp[i][j][0] += dp[i][j-1][0] + dp[i][j-1][1];
                dp[i][j][1] += dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2];
                dp[i][j][2] += dp[i-1][j][1] + dp[i-1][j][2];       
        }
    }

 

그럼 이걸로 끝일까??

 

 

 

모두 아시겠지만 한 가지 놓친 조건이 있다.

각 칸에는 빈 칸(0)도 올 수 있지만, 벽(1)도 올 수 있다!

벽일 때는 파이프가 이어질 수 없으므로 그 조건을 적용해줘야 한다.

 

 

우리는 파이프의 끝을 계속 활용해주고 있으므로 끝이 1이 아니어야 한다는 것은 자명하다.

if(map[i][j] != 1)

 

 

 

하지만, 가로와 세로는 이 조건으로 해결되는 반면

대각선의 경우는 파이프 끝의 한 칸 위와 한 칸 왼쪽 칸도 벽이 아니어야 파이프가 연결될 수 있다.

 

이걸 식으로 표현하면 다음과 같다

if(map[i][j] != 1 && map[i-1][j] != 1 && map[i][j-1] != 1)

 

 

그럼 이제 진짜 답을 구할 수 있을 것 같다.

dp[n][n][0] + dp[n][n][1] + dp[n][n][2]의 값을 더해주면

(n,n)까지 이동시키는 경우의 수가 나올 것이다!!

 

 

전체 코드

#include <iostream>
#include <algorithm>
using namespace std;

int map[20][20];
int dp[20][20][3];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin>>map[i][j];
        }
    }

    dp[1][2][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(map[i][j] != 1){
                dp[i][j][0] += dp[i][j-1][0] + dp[i][j-1][1];
                if(map[i-1][j] != 1 && map[i][j-1] != 1) dp[i][j][1] += dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2];
                dp[i][j][2] += dp[i-1][j][1] + dp[i-1][j][2];
            }
            
        }
    }
    
    int ans = 0;
    for(int k = 0; k < 3; k++){
        ans += dp[n][n][k];
    }
    cout<<ans;
    return 0;
}