![[프로그래머스] 등굣길 (Java, DP, lv3)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FdycLVJ%2FbtsIKSKB0yl%2FP2IkXB9fWwDV2PnxYaF5rk%2Fimg.png)

[프로그래머스] 등굣길 (Java, DP, lv3)알고리즘/동적 프로그래밍2024. 7. 23. 13:57
반응형

문제 출처
https://school.programmers.co.kr/learn/courses/30/lessons/42898
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 풀이
- 동적 프로그래밍 (Dynamic Programming) 문제
- 시간 복잡도 : O(NM)
- 격자형 그래프가 주어졌을 때 (1,1) -> (n, m)으로 이동하는 경우의 수를 구하는 문제
- 이때 이동 방향은 오른쪽과 아래쪽으로만 이동가능하다
① dp 배열을 정의하고, 물 웅덩이 영역을 -1로 표시한다 (이때 puddles가 m,n으로 주어져서 주의 필요)
int row = n;
int col = m;
int[][] dp = new int[row + 1][col + 1];
for(int[] p : puddles) {
dp[p[1]][p[0]] = -1; // 물 웅덩이 표시
}
② (1,1)에서 오른쪽과 아래 영역을 초기화한다.
이때 물 웅덩이(-1) 만날 경우 이동 방향 제한으로 못 가므로 break 종료한다
for(int i = 1; i <= col; i++) {
if(dp[1][i] == -1) break;
dp[1][i] = 1;
}
for(int i = 1; i <= row; i++) {
if(dp[i][1] == -1) break;
dp[i][1] = 1;
}

③ 2중 반복문을 돌면서 값을 갱신한다
예. (2,3)의 경우 왼쪽(2,2)에서 오는 경우와 위(1,3)에서 오는 경우에서 왼쪽은 물웅덩이므로 합산하지 x
그리고 합산시 mod(1억 7)로 나눠주도록 한다

int mod = 1_000_000_007;
for(int i = 2; i <= row; i++) {
for(int j = 2; j <= col; j++) {
if(dp[i][j] == -1) continue; // 물 웅덩이인 경우
if(dp[i - 1][j] != -1) { // 위가 물웅덩이가 아닌 경우
dp[i][j] += dp[i - 1][j];
dp[i][j] %= mod;
}
if(dp[i][j - 1] != -1) { // 왼쪽이 물웅덩이가 아닌 경우
dp[i][j] += dp[i][j - 1];
dp[i][j] %= mod;
}
}
}

④ 최종적으로 dp[n][m] 결과를 반환한다
전체 코드
import java.util.*;
class Solution {
public int solution(int m, int n, int[][] puddles) {
int answer = 0;
int mod = 1_000_000_007;
int row = n;
int col = m;
int[][] dp = new int[row + 1][col + 1];
for(int[] p : puddles) {
dp[p[1]][p[0]] = -1; // 물 웅덩이 표시, m, n 위치 주의 *
}
for(int i = 1; i <= col; i++) {
if(dp[1][i] == -1) break;
dp[1][i] = 1;
}
for(int i = 1; i <= row; i++) {
if(dp[i][1] == -1) break;
dp[i][1] = 1;
}
for(int i = 2; i <= row; i++) {
for(int j = 2; j <= col; j++) {
if(dp[i][j] == -1) continue;
if(dp[i - 1][j] != -1) {
dp[i][j] += dp[i - 1][j];
dp[i][j] %= mod;
}
if(dp[i][j - 1] != -1) {
dp[i][j] += dp[i][j - 1];
dp[i][j] %= mod;
}
}
}
return dp[row][col];
}
}
반응형
'알고리즘 > 동적 프로그래밍' 카테고리의 다른 글
[프로그래머스] 사칙연산 (Java, DP, lv4) (1) | 2024.07.24 |
---|---|
[프로그래머스] N으로 표현 (Java, DP, lv3) (0) | 2024.07.23 |
[BOJ2011] 암호코드 (다이나믹 프로그래밍) (1) | 2024.02.27 |
[BOJ15991] 1,2,3더하기 6(동적 프로그래밍) (1) | 2024.02.26 |
[BOJ21923] 곡예 비행 (동적 프로그래밍) (0) | 2023.10.06 |

@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!