[백준 문제풀이] 5569 출근 경로 java풀이

문제

상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다.

남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대로 번호가 1, 2, ..., h로 매겨져 있다. 서쪽에서 i번째 남북 방향 도로와 남쪽에서 j번째 동서 방향 도로가 만나는 교차로는 (i, j)이다.

상근이는 교차로 (1, 1)에 살고 있고, 교차로 (w, h)에 있는 회사에 차로 다니고 있다. 차는 도로로만 이동할 수 있다. 상근이는 회사에 최대한 빨리 가기 위해서, 동쪽 또는 북쪽으로만 이동할 수 있다. 또, 이 도시는 교통 사고를 줄이기 위해서 교차로를 돈 차량은 그 다음 교차로에서 다시 방향을 바꿀 수 없다. 즉, 교차로에서 방향을 바꾼 후, 1 블록만 이동한 후 다시 방향을 바꿀 수 없다.

상근이가 회사에 출근할 수 있는 경로의 수는 몇 가지 일까?

w와 h가 주어졌을 때, 가능한 출근 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 w와 h가 주어진다. (2 ≤ w, h ≤ 100)

출력

첫째 줄에 상근이가 출근할 수 있는 경로의 개수를 100000로 나눈 나머지를 출력한다.

 

힌트

 

접근법 : 

1) 어떻게 풀 것인가?

 

이 문제는 알고리즘 수업을 듣던 중 풀게 된 문제이다.

내가 지금까지 겪어본 dp문제는 항상  "dp[i][j]는 i,j까지 오는데 걸리는 최댓값이다"라는 공식을 벗어나지 않았기때문에 이 문제도 처음에

2차원 배열로 풀려고 했다. 

내가 생각했던 방법은 아래와 같다. 

1. Arraylist를 가지는 2차원 배열을 만든다. 

2. 이 arraylist는 "up"과 "right"를 담는 길이가 3인 stirng[] 배열을 담는다. 

3. 만약 up right up / right up right 가 연속된다면 문제에서 말하는 교차로를 돈다는 내용이므로 제외한다...

 

등....이런식으로 생각했는데 이렇게 되면 너무 복잡해지고, 문제 풀 당시에 내가 글씨로 정리하면서도 로직을 짜면 짤수록 허점이 보였다. 

(단순 up, right의 개수가 아니라 이들의 연속성이 중요하다)

그래서 강사님의 힌트를 기다렸는데, 강사님께서 3차원 배열을 사용하라고 하셨다. 

헉.....솔직히 생각도 못했다. 창피했다...

 

2) 시간복잡도

이 문제는 시간 복잡도가 어떻게 되는지 모르겠다.... O(wh)인가?

그러면 w,h 모두 100이하기때문에 괜찮을것같다. 

( 질문게시판에 물어봐야지..)

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

위에서 말함..

dp로 이차원 배열만 생각한것

 

5) 이 문제를 통해 얻어갈 것

나는 프로그램상에서 경우의 수를 제거하는걸 생각했는데

이 문제는 짜는 사람이 되는 경우와 안 되는 경우를 미리 생각하고 되는 경우만 넣는 문제였다 .

검색해보니 격자식문제의 기본문제라고 하던데..한번 알아봐야겠다.

 

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


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = br.readLine().split(" ");
        int w = Integer.parseInt(strings[0]);
        int h = Integer.parseInt(strings[1]);
        int[][][][] dp = new int[w + 1][h + 1][2][2];
        int MOD = 100000;
// 파스칼 삼각형 깔기 (어차피 다 1임)
        for (int i = 1; i <= w; i++) {
            dp[i][1][0][0] = 1;
        }
        for (int i = 1; i <= h; i++) {
            dp[1][i][1][0] = 1;
        }

        for (int i = 2; i <= w; i++) {
            for (int j = 2; j <= h; j++) {
                //[0 오른쪽 1 위쪽][0 안 꺾임 1 꺾임]
                // 직접 그려보며 하는걸 추천(이해하는데 한참 걸림.. 블로그 정리할것)
                dp[i][j][0][0] = (dp[i-1][j][0][0] + dp[i-1][j][0][1])%MOD;
                dp[i][j][0][1] = dp[i-1][j][1][0] % MOD;
                dp[i][j][1][0] = (dp[i][j-1][1][0] + dp[i][j-1][1][1])%MOD;
                dp[i][j][1][1] = dp[i][j-1][0][0] % MOD;
            }
        }
       int sum = (dp[w][h][0][0] + dp[w][h][0][1] + dp[w][h][1][0] + dp[w][h][1][1])%MOD;
        System.out.println(sum);
    }
}