파이프 옮기기 1 (feat. 백준, 17070번)

파이프 옮기기 1
https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <numeric>
using namespace std;
int N, arr[17][17], dp[17][17][3];      //dp의 3은 0:가로, 1:대각선, 2:세로
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    memset(dp, 0, sizeof(dp));
    dp[1][2][0] = 1;
    cin >> N;
    for(register int i = 1, j; i <= N; ++i)
        for(j = 1; j <= N; ++j)
            cin >> arr[i][j];
    for(register int i = 1, j; i <= N; ++i)
        for(j = 1; j <= N; ++j) {
            // 가로 방향으로 체크
            if(j + 1 <= N && arr[i][j + 1] == 0)
                dp[i][j + 1][0] += (dp[i][j][0] + dp[i][j][1]);
            // 세로 방향으로 체크
            if(i + 1 <= N && arr[i + 1][j] == 0)
                dp[i + 1][j][2] += (dp[i][j][1] + dp[i][j][2]);
            // 대각 방향으로 체크
            if(i + 1 <= N && j + 1 <= N && arr[i][j + 1] == 0 && arr[i + 1][j] == 0 && arr[i + 1][j + 1] == 0)
                dp[i + 1][j + 1][1] += (dp[i][j][0] + dp[i][j][1] + dp[i][j][2]);
        }
    cout << accumulate(dp[N][N], dp[N][N] + 3, 0);
    return 0;
}
// *&)*@*

 

 

굉장히 좋은 dp 문제를 푼것 같습니다. dp에 대해서 파악하기에 적합하다고 생각했습니다.

1. 현재 내 위치는 이전의 가로, 세로, 대각 으로부터 올 수 있습니다. 따라서 dp는 가로,세로,대각 에 대해 각각 두었습니다.
2. 현재 내 위치의 dp[가로]는 이전의 dp[가로] + 이전의 dp[대각] 입니다. (세로도 마찬가지입니다.)
   현재 내 위치의 dp[대각]은 이전의 dp[가로] + 이전의 dp[세로] + 이전의 dp[대각] 입니다.
3. 주의할 점은 이전의 dp[가로,세로,대각]이 벽이 아닌 경우만 위 연산이 이루어진다는 것입니다.