[Baekjoon] 출근 경로

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

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

public class Main{

    private static final int MOD = 100_000;
    private static int w,h,answer;
    private static int[][][][] dp;

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

        init();

        sol();

        print();
    }

    private static void sol(){

        for(int y=2; y<=h; y++){

            for(int x=2; x<=w; x++){

                // [0 : 위쪽 1: 오른쪽] [0 : 안 꺾음 1: 꺾음]
                dp[y][x][0][0] = (dp[y-1][x][0][0] + dp[y-1][x][0][1]) % MOD;
                dp[y][x][0][1] = dp[y-1][x][1][0] % MOD;
                dp[y][x][1][0] = (dp[y][x-1][1][0] + dp[y][x-1][1][1]) % MOD;
                dp[y][x][1][1] = dp[y][x-1][0][0] % MOD;
            }
        }

        answer = (dp[h][w][0][0] + dp[h][w][0][1] + dp[h][w][1][0] + dp[h][w][1][1]) % MOD;
    }

    private static void init()throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        StringTokenizer st = new StringTokenizer(br.readLine());

        w = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());

        // 1,1에서 w,h 까지 가는 경우의 수 이므로 h,w가 바뀌어도 값은 똑같다
        dp = new int[h+1][w+1][2][2];

        // 1,w 까지 가는 경우의 수 -> y값이 1이기 때문에 경우의 수는 한가지 뿐이다.
        for(int i=1; i<=h; i++){

            dp[i][1][0][0] = 1;
        }

        for(int i=1; i<=w; i++){

            dp[1][i][1][0] = 1;
        }

    }

    private static void print()throws IOException{

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(String.valueOf(answer));
        bw.close();
    }
}

주요 개념

• DP

접근 방식

• 4차원 DP에서 앞에서 2번째 까지는 단순한 좌표다.

• 3번째부터 4번째는 순서대로 오른쪽/위쪽 여부와 방향 전환 여부를 뜻한다.

  • 복잡해 보이지만 오른쪽과 위쪽으로 경우의 수가 2배로 늘어났기 때문에 실질적으로 방향 전환 여부만 확인하면 된다.

  • dp[y][x][0][0] = (dp[y-1][x][0][0] + dp[y-1][x][0][1]) % MOD;

    (y,x) 좌표에서 위쪽으로 꺾지 않는 경우의 수는

    바로 직전 좌표까지 꺾지 않고 오는 수와 꺾은 수의 합이다.

  • dp[y][x][0][1] = dp[y-1][x][1][0] % MOD;

    (y,x) 좌표에서 위쪽으로 꺾어서 오는 경우의 수는

    문제 조건으로 인해 최소한 꺾여서 오면 안된다.

    또한 위쪽으로 꺾여야 하기 때문에 위쪽으로 오는 경우의 수도 제외해야 한다.

    따라서 오른쪽으로 가면서 꺾지 않은 경우의 수가 와야한다.

  • 나머지는 동일한 개념을 적용하면 된다.

• 갑자기 4차원 까지 나와서 당황했지만 벽 부수고 이동하기 문제 시리즈에서 단계가 높아 질수록 방문 배열의 정보가 단순 2차원 배열에서 3차원 배열로 늘어나는 것과 비슷한 결이라고 생각한다.

• 2차원 좌표를 기준으로 경우의 수가 분기하는 조건만큼 차원 수를 늘린다고 생각하면 될 것 같다.