[Java] 프로그래머스 동적계획법(Dynamic Programming) Lv3 - 등굣길

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

코딩테스트 연습 - 등굣길

 

오늘의 문제는 살짝... 당황스러운 문제였다....😂

 

✔ 입출력 예시

등굣길 입출력 예시

 

💡 포인트

1️⃣ 직사각형 M * N이 제시되어 map의 열이 먼저 제시되고 다음으로 행이 제시

2️⃣ 마찬가지로 puddles 배열의 인덱스는 (m, n) (puddles[i][0] = 열, puddles[i][1] = 행)

3️⃣ 효율성을 위해 각 계산 과정마다 %1,000,000,007을 해주어야 함 

 

 

✔ 소스코드

package DP;

public class wayToSchool { // 등굣길

	public static void main(String[] args) {
		int m = 4;
		int n = 3;
		int[][] puddles = { { 2, 2 } };

		System.out.println(solution(m, n, puddles));
	}

	private static int solution(int m, int n, int[][] puddles) {
		int answer = 0;
		
		int[][] memo = new int[n+1][m+1];  // 갈 수 있는 길의 수 메모
		
		for (int i = 0; i < puddles.length; i++) {
			memo[puddles[i][0]][puddles[i][1]] = -1;
		}
		
		memo[1][1] = 1;
		
//		for (int i = 1; i < memo.length; i++) {
//			for (int j = 1; j < memo[i].length; j++) {
//				System.out.print(memo[i][j]);
//			}System.out.println();
//		}
		
		for (int i = 1; i < n+1; i++) {
			for (int j = 1; j < m+1; j++) {
				if(memo[i][j] == -1) {
//					System.out.println(memo[i][j] + "입니다");
					continue;
				}
				if(memo[i][j-1] >= 0 && memo[i][j] >= 0) {  // 이전(왼쪽)에 숫자가 0이상이면 더하기
					memo[i][j] = memo[i][j] + memo[i][j-1] % 1000000007;  
				}
				if(memo[i-1][j] >= 0 && memo[i][j] >= 0) {  // 이전(위쪽)에 숫자가 0이상이면 더하기
					memo[i][j] = memo[i][j] + memo[i-1][j] % 1000000007;
				}
			}
		}
		
//		for (int i = 1; i < memo.length; i++) {
//			for (int j = 1; j < memo[i].length; j++) {
//				System.out.print(memo[i][j]);
//			}System.out.println();
//		}
//		
		answer = memo[n][m] % 1000000007;
		
		return answer;
	}

}

 

각 최단경로의 수를 구해줄 때마다 %1,000,000,007을 해주지 않아서 틀리기도 하고

puddles 배열의 인덱스가 행과 열이 바뀐지 모르고 제출했다가 또 틀렸다가

겨우 맞을 수 있었다...😂