백준 17069번 - 파이프 옮기기 2

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

17069번: 파이프 옮기기 2

 

 

 

 

 

9월 30일 풀이

 

 

 

 

 

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

17070번: 파이프 옮기기 1

 

 

 

 

 

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

public class b17069 {
	static int N;
	static int[][] graph;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		graph = new int[N + 1][N + 1];
		
		for(int i = 1; i < N + 1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			for(int j = 1; j < N + 1; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//구현
		long[][][] dp = new long[N + 1][N + 1][3]; //0 : 가로, 1 : 세로, 2: 대각선
		
		dp[1][2][0] = 1;
		
		for(int i = 1; i <= N; i++) {
			for(int j = 3; j <= N; j++) {
				if(graph[i][j] != 1) {
					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];
					
					if(graph[i - 1][j] != 1 && graph[i][j - 1] != 1) {
						dp[i][j][2] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];
					}
				}
			}
		}
		
		long answer = dp[N][N][0] + dp[N][N][1] + dp[N][N][2];
		
		System.out.println(answer);
	}

}