[백준] 17069 파이프 옮기기 2 - DP JAVA

https://www.acmicpc.net/problem/17069

17069번: 파이프 옮기기 2

코드설명

DP 문제입니다.

 

DP[Row][Col][3] 이라할때, 파이프(Row, Col)을 끝점으로 하며 0, 1, 2 의 방향으로 존재할 수 있는 경우의 수를 의미합니다.

예시로, DP[1][3][0] 일경우 (1,3)을 끝점으로 하는 파이프가 오른쪽을 바라보려면, DP[1][3][0] = DP[1][2][0] + DP[1][2][1] 로 처리할 수 있습니다. 왼쪽 칸에서 오른쪽방향일경우와 왼쪽 칸에서 대각선일경우를 의미합니다. (대각선일경우에는45도로 위로 회전시킨다는 의미입니다.)

 

오른쪽 방향을 향하는 끝점이 Row, Col인 파이프의 개수는 왼쪽 칸에서 가로와 대각일 때만 가능합니다.

대각선 방향을 향하는 끝점이 Row, Col 인 파이프의 개수는 대각선 방향에서 오른쪽, 대각선, 아래쪽 방향일때 가능합니다.

하 방향을 향하는 끝점이 Row, Col인 파이프의 개수는 위 칸에서 대각선, 아래쪽 방향일때만 가능합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int T, N;
	public static int[][] map;
	public static long[][][] DP;
	public static long answer = 0;
	public static int[] dx = {-1, -1, 0}; //상, 좌대각, 좌
	public static int[] dy = {0, -1, -1};
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	map = new int[N+1][N+1];
    	DP = new long[N+1][N+1][3];
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=1;j<=N;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	//0:가로파이프, 1:대각선파이프, 2: 세로파이프
    	DP[1][2][0] = 1;
    	for(int i=1;i<=N;i++) {
    		for(int j=3;j<=N;j++) {
    			
				if(map[i][j] == 0) {
					DP[i][j][0] = DP[i][j-1][0] + DP[i][j-1][1];	
				}
				
				if(map[i][j] == 0 && map[i-1][j] == 0 && map[i][j-1] == 0) {
					DP[i][j][1] = DP[i-1][j-1][0] + DP[i-1][j-1][1] + DP[i-1][j-1][2];
				}
				
				if(map[i][j] == 0) {
					DP[i][j][2] = DP[i-1][j][2] + DP[i-1][j][1];
				}
					
    		}
    	}
    	System.out.println(DP[N][N][0] + DP[N][N][1] + DP[N][N][2]);
    	
    	
	}
	
	

}