[백준] 파이프 옮기기 (골드4-5)

https://www.acmicpc.net/problem/17070
시뮬레이션 방식으로 풀이

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

public class Main {
    static int n, ans;
    static int[][] map;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1;j<=n;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 가능하면 개수 출력
        pipe(1,2,0);

        System.out.println(ans);
    }

    static void pipe(int r, int c, int dis){
        if(r==n && c==n){
            ans += 1;
            return;
        }

        if(dis==0 || dis==2){ // 가로
            if(c+1<=n && map[r][c+1]!=1)
                pipe(r,c+1,0);
        }
        if(dis==1 || dis==2){ // 세로
            if(r+1<=n && map[r+1][c]!=1)
                pipe(r+1,c,1);
        }
        if(r+1<=n && c+1<=n && map[r+1][c]==0 && map[r][c+1]==0 && map[r+1][c+1]==0)
            pipe(r+1,c+1,2);

    }
}

https://www.acmicpc.net/problem/17069
dp 방식

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// DP
public class Main {
    static int N;
    static int[][] map;
    static int[][][] memoi;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        map = new int[N + 1][N + 1]; // 0 dummy
        
        // 좌표 4,3 으로 이동하는 모든 방법은 아래 3개를 합친다.
        // memoi[0][4][3] : 대각선으로 4,3 으로 이동하는 경우의 수 (누적합)
        // memoi[1][4][3] : 가로로 4,3 으로 이동하는 경우의 수 (누적합)
        // memoi[2][4][3] : 세로로 4,3 으로 이동하는 경우의 수 (누적합)
        memoi = new int[3][N + 1][N + 1];
        
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // dp
        // * X
        // X X
        memoi[1][1][2] = 1; // 가로, 시작 좌표
        
        for (int y = 1; y <= N; y++) {
            for (int x = 2; x <= N; x++) {
                // 벽
                if( map[y][x] == 1 ) continue;
                
                // 대각선
                if( y < N && x < N && map[y + 1][x + 1] == 0 && map[y + 1][x] == 0 && map[y][x + 1] == 0) {
                    memoi[0][y + 1][x + 1] += ( memoi[0][y][x] + memoi[1][y][x] + memoi[2][y][x]);
                }
                // 가로
                if( x < N && map[y][x + 1] == 0 ) {
                    memoi[1][y][x + 1] += ( memoi[0][y][x] + memoi[1][y][x] );
                }
                // 세로
                if( y < N && map[y + 1][x] == 0 ) {
                    memoi[2][y + 1][x] += ( memoi[0][y][x] + memoi[2][y][x] );
                }
            }
        }
        
        System.out.println(memoi[0][N][N] + memoi[1][N][N] + memoi[2][N][N]);
    }
}