[JAVA]백준 17070번: 파이프 옮기기 1

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

1. 문제 설명

 

파이프를 옮기려고 할 때 파이프는 45도만 회전시킬 수 있다. 가장 처음 파이프는 (1,1)와 (1,2)를 차지하고 있고 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

 

2. 풀이

 

dp[X][Y][3] -> (X, Y)까지 파이프를 이동시킬 수 있는 방법의 수

 

0 -> 가로, 1-> 세로, 2-> 대각선이라고 하자.

 

그렇다면

dp[x][y][0] += dp [x][y - 1][0] + dp[x][y - 1][2]
dp[x][y][1] += dp [x - 1][y][1] + dp[x - 1][y][2]
dp[x][y][2] += dp [x - 1][y - 1][0] + dp[x - 1][y - 1][1] + dp[x - 1][y - 1][2]이다.

 

자세한 사항은 그림을 참고하면 바로 알 수 있다. 

 

 

3. 코드

import java.io.*;
import java.util.*;

public class Main {


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int size = Integer.parseInt(br.readLine());

        int[][] wall = new int[size + 1][size + 1];
        int[][][] dp = new int[size + 1][size + 1][3];

        for (int x = 1; x <= size; x++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int y = 1; y <= size; y++) {
                wall[x][y] = Integer.parseInt(st.nextToken());
            }
        }


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

        for (int x = 1; x <= size; x++) {
            for (int y = 1; y <= size; y++) {

                if(wall[x][y]==1)
                    continue;

                dp[x][y][0] += dp[x][y - 1][0] + dp[x][y - 1][2];
                dp[x][y][1] += dp[x - 1][y][1] + dp[x - 1][y][2];

                if (wall[x - 1][y] == 0 && wall[x][y - 1] == 0) {
                    dp[x][y][2] += dp[x - 1][y - 1][0] + dp[x - 1][y - 1][1] + dp[x - 1][y - 1][2];
                }

            }
        }

        System.out.println(dp[size][size][0] + dp[size][size][1] + dp[size][size][2]);

        br.close();


    }

}