[DP] 등굣길 - JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

---

우선 이 문제는 욕을 엄~청 먹고 있더라구

그래서 왜그럴까 했는데 욕먹을만 했어

보통 mXn 배열이면 arr[m][n] 이라고 생각하잖아

근데 얜 반대야

arr[n][m]임

그니까 n이 행이고 m이 열이야

게다가 그 웅덩이 위치도 행열을 반대로 알려줘

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

화낼만 하더라....

 

그리고 두 번째로 화나는 거는 이게 최단 거리를 1,000,000,007 로 나눈 나머지를 return해야 되는데

DP를 구하는 과정에서도 계속 나눠서 구해줘야 되는거?

코드 보면 알겠지만 배열에 값을 저장할 때마다 저걸로 나눈 나머지를 저장하고 있거든?

근데 이 이유가 Integer 범위를 벗어날 수 있어서 저렇게 저장해줘야 효율성이 맞는대

음..... 근데 코테에서 이렇게 나눠라 하는 문제들은 대부분 이래야 통과하더라구

쉽지 않다... 암튼!

 

 

최단거리...

그 초등학교 때 배우는 최단거리 구하는 방법 알아?

그걸로 하면 되는데 그림으로 보면

 

요렇게 구하는거 알아?

예를 들어 arr[1][1]은 arr[0][1]이랑 arr[1][0]값을 더한 값인거지

즉, 그 위치까지의 최단 거리는 그 위치의 왼쪽과 위쪽까지의 최단거리를 더한 값이랑 같은거야

예전에 이걸로 최단거리 엄청 구했는데....~.~

 

암튼 이거 이용할 건데 문제에 웅덩이가 있어

그래서 처음에 웅덩이를 -1로 초기화해두고

반복문 돌면서 웅덩이 만나면 웅덩이 부분은 0으로 초기화해줘

왜? 못지나가니까~!~~!

그리고 계속 왼쪽 위쪽 더해주면 돼

여기서 주의할 점은?? 나눈 값의 나머지 저장해주기~~

 

 

 

 

자바 코드)

import org.junit.Assert;
import org.junit.Test;

public class DP3 {
    public int solution(int m, int n, int[][] puddles) {
        int mod = 1000000007;
        int[][] arr = new int[n][m];

        for(int[] puddle : puddles) { // 웅덩이
            arr[puddle[1]-1][puddle[0]-1] = -1;
        }

        arr[0][0] = 1; // 출발점 초기화

        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(arr[i][j]==-1) { // 웅덩이면 0으로 바꾸고 continue
                    arr[i][j] = 0;
                    continue;
                }

                if(i!=0) { // 위쪽 값 더해주기
                    arr[i][j] += arr[i-1][j] % mod;
                }

                if(j!=0) { // 왼쪽 값 더해주기
                    arr[i][j] += arr[i][j-1] % mod;
                }
            }
        }
        return arr[n-1][m-1] % mod;
    }

    @Test
    public void test() {
        Assert.assertEquals(4, solution(4, 3, new int[][]{{2,2}}));
        Assert.assertEquals(7, solution(4, 4, new int[][]{{3,2}, {2,4}}));
        Assert.assertEquals(7, solution(5, 3, new int[][]{{4,2}}));
        Assert.assertEquals(0, solution(2, 2, new int[][]{{2,1}, {1, 2}}));
        Assert.assertEquals(0, solution(3, 1, new int[][]{{2,1}}));

    }
}

끝!