[백준] 17070 - 파이프 옮기기 1

1. 문제

17070번: 파이프 옮기기 1

2. 개요

1,1 1,2를 차지하고 있는 파이프를 회전, 이동시켜 N, N까지 도착하게 하는 경우의 수를 구하는 문제.

파이프의 방향은 가로, 세로, 우하향 대각선의 세 방향만 가능하다.

3. 풀이 및 코드

3-1. 풀이

파이프의 방향을 저장할 dp테이블을 만든다. 세 방향이 가능하므로 각 칸마다 3칸짜리를 만들어

N * N * 3 크기의 dp테이블이 만들어지게 된다.

처음에 파이프가 가로로 놓여져있으므로 맨 윗줄을 벽이 없다면 가로로 채워넣는다.

다음은 현재 칸과 좌측, 상단이 벽이 없는 경우에 좌 상단 위치의 파이프의 모든 방향을 더해 대각선을 채워넣는다.

다음으로 다시 가로, 세로가 가능한 경우를 dp테이블에 더해 넣는다.

모든 칸에 대한 연산을 마쳤다면, 마지막 칸의 모든 경우를 더한 값을 답으로 출력한다.

3-2. Python

import sys

N = int(sys.stdin.readline())

table = []

for i in range(N):
    table.append(list(map(int, sys.stdin.readline().split())))

dp = [[[0, 0, 0] for i in range(N)] for i in range(N)]
dp[0][0][0] = 1
dp[0][1][0] = 1

for i in range(2, N):
    if table[0][i] == 0:
        dp[0][i][0] = dp[0][i-1][0]

for i in range(1, N):
    for j in range(2, N):
        if table[i][j] == 0 and table[i-1][j] == 0 and table[i][j-1] == 0:
            dp[i][j][2] = sum(dp[i-1][j-1])

        if table[i][j] == 0:
            dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2]
            dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2]

print(sum(dp[N-1][N-1]))

3-3. C#

using System.Diagnostics;

namespace boj_17070
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int N = int.Parse(sr.ReadLine());

            List<List<int>> table = new List<List<int>>();

            for (int i = 0; i < N; i++)
                table.Add(Array.ConvertAll(sr.ReadLine().Split(), int.Parse).ToList());

            int[,,] dp = new int[N, N, 3];

            dp[0, 0, 0] = 1;
            dp[0, 1, 0] = 1;

            for (int i = 2; i < N; i++)
            {
                if (table[0][i] == 0)
                    dp[0, i, 0] = dp[0, i - 1, 0];
            }

            for (int i = 1; i < N; i++)
            {
                for (int j = 2; j < N; j++)
                {
                    if (table[i][j] == 0 && table[i - 1][j] == 0 && table[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];
                    }

                    if (table[i][j] == 0)
                    {
                        dp[i, j, 0] = dp[i, j - 1, 0] + dp[i, j - 1, 2];
                        dp[i, j, 1] = dp[i - 1, j, 1] + dp[i - 1, j, 2];
                    }
                }
            }

            sw.WriteLine(dp[N - 1, N - 1, 0] + dp[N - 1, N - 1, 1] + dp[N - 1, N - 1, 2]);
            sw.Close();
        }
    }
}