17070번: 파이프 옮기기 1

17070번: 파이프 옮기기 1

사용 언어: C++

문제 요약

문제 요약이 어려우므로 문제 확인 요망

풀이

DP로 테이블을 채우면서 파이프를 옮기면 해당 칸 업데이트.

dp[r][c][dir]: 파이프 끝이 (r, c)에 있고, dir 방향일 때의 경우의 수. (dir 0 : 가로, 1 : 세로, 2 : 대각선)

예를 들어 시작이 (1,1), (1,2)에 파이프가 하나 있으니까 dp[1][2][0] = 1;로 초기화하는 것.

또한, 이 문제는 오른쪽과 아래, or 오른쪽-아래로만 움직이니까 dp[1][2]면 자동으로 (1,1)에 다른 쪽 파이프가 있다고 가정 가능.

답

#include <iostream>
#include <vector>

using namespace std;

int N;
int house[17][17];
int dp[17][17][3];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    // 시작 위치 초기화: (1, 2)에 가로 방향으로 놓인 파이프 1개
    dp[1][2][0] = 1;

    // DP 테이블 채우기
    for (int i = 1; i <= N; i++) 
    {
        for (int j = 3; j <= N; j++) 
        {
            // 현재 칸 (i, j)가 벽이면 파이프를 놓을 수 없음
            if (house[i][j] == 1) continue;

            // 1. (i, j)에 가로 방향으로 도착하는 경우
            // (i, j-1)에서 오른쪽으로 이동. 이전 파이프는 가로 또는 대각선.
            dp[i][j][0] = dp[i][j - 1][0] + dp[i][j - 1][2];

            // 2. (i, j)에 세로 방향으로 도착하는 경우
            // (i-1, j)에서 아래로 이동. 이전 파이프는 세로 또는 대각선.
            dp[i][j][1] = dp[i - 1][j][1] + dp[i - 1][j][2];

            // 3. (i, j)에 대각선 방향으로 도착하는 경우
            // (i-1, j-1)에서 대각선으로 이동. 이전 파이프는 가로, 세로, 대각선 모두 가능.
            // 대각선 이동은 주변 칸 (i-1, j)와 (i, j-1)도 비어있어야 함.
            if (house[i - 1][j] == 0 && house[i][j - 1] == 0) 
            {
                dp[i][j][2] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];
            }
        }
    }

    // 최종 결과: (N, N)에 도달하는 모든 방향의 경우의 수 합
    int result = dp[N][N][0] + dp[N][N][1] + dp[N][N][2];
    cout << result << '\n';

    return 0;
}