[백준 17069번] 파이프 옮기기 2 (C++)

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

17069번: 파이프 옮기기 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
ll arr[33][33];
ll dp[33][33][3]; //0 : 가로, 1 : 세로, 2 : 대각선

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    dp[1][2][0] = 1; //초기위치
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            cin >> arr[i][j];
            if(i==1 && j<=2) continue;
            if(arr[i][j]==1) continue; //벽이면 불가능
            dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2]; //가로 -> 가로 or 대각선 -> 가로
            dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2]; //세로 -> 세로 or 대각선 -> 세로
            if(arr[i][j-1] || arr[i-1][j]) continue; //대각선의 경우 추가 검토 (왼쪽, 위)
            dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]; //가로 -> 대각선 or 세로-> 대각선 or 대각선 -> 대각선
        }
    }

    cout << dp[N][N][0] + dp[N][N][1] + dp[N][N][2];
    return 0;
}

 

백준 17070번 파이프 옮기기 1번과 동일한 로직으로 풀리는 문제이다.

단순히 값의 범위(long long)와 주어진 N 범위만 다르고 나머지는 동일하게 하여 풀었다.

참고링크 : https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

17070번 문제와 같은 경우 dp 말고 bfs로도 풀 수 있는 문제였는데 만약 해당 문제를 dp로 풀었었다면 이번 문제도 범위만 살짝 조절하면 동일하다 싶이 풀 수 있다.