[BJ] 17069. 파이프옮기기2

BJ 17069. 파이프 옮기기2

 

 

문제링크

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

17069번: 파이프 옮기기 2

 

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/mlzigFZAoAI

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l5;

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


public class BJ_G5_17069_파이프옮기기2 {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder output = new StringBuilder();
    private static StringTokenizer tokens;

    static int N;
    static int[][] map;

    static int HOR = 0, VER = 1, DIA = 2;
    static long C;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(instr));
        N = Integer.parseInt(input.readLine()) + 1;
        map = new int[N][N];
        for (int r = 1; r < N; r++) {
            tokens = new StringTokenizer(input.readLine());
            for (int c = 1; c < N; c++) {
                map[r][c] = Integer.parseInt(tokens.nextToken());
            }
        }
        dp();
        System.out.println(C);
    }

    static void dp() {
        // 값을 저장할 동적 테이블 작성
        // r, c를 d의 방향에서 방문한 경우의 수
        long[][][] dp = new long[N][N][3];
        // 최초의 기저 값
        dp[1][2][HOR] = 1;

        for (int r = 1; r < N; r++) {
            for (int c = 3; c < N; c++) {
                // 체크 대상 지점은 공백!
                if (map[r][c] == 1) {
                    continue;
                }
                // 현재 지점에 가로로 온 경우: 왼쪽 지점에 가로 또는 대각선으로 온 경우
                dp[r][c][HOR] = dp[r][c - 1][HOR] + dp[r][c - 1][DIA];
                // 현재 지점에 세로로 온 경우: 윗쪽 지점에 세로 또는 대각선으로 온 경우
                dp[r][c][VER] = dp[r - 1][c][VER] + dp[r - 1][c][DIA];
                // 현재 지점에 대각으로 온 경우: 왼쪽윗쪽 지점에 가로, 세로, 대각으로 온 경우
                if (map[r - 1][c] == 0 && map[r][c - 1] == 0) {
                    dp[r][c][DIA] = dp[r - 1][c - 1][HOR] + dp[r - 1][c - 1][VER] + dp[r - 1][c - 1][DIA];
                }
            }
        }
        C = dp[N - 1][N - 1][HOR] + dp[N - 1][N - 1][VER] + dp[N - 1][N - 1][DIA];
    }

    // REMOVE_START
    private static String instr = "6\r\n" +
                                  "0 0 0 0 0 0\r\n" +
                                  "0 1 0 0 0 0\r\n" +
                                  "0 0 0 0 0 0\r\n" +
                                  "0 0 0 0 0 0\r\n" +
                                  "0 0 0 0 0 0\r\n" +
                                  "0 0 0 0 0 0";
    // REMOVE_END
}