- 사용 알고리즘 : Dynamic Programming(동적 계획법)
- 맵의 크기보다 행 + 1, 열 + 1 크기만큼 크게 만든다.
- 시작 위치(1, 1)는 넘어가고, 물 웅덩이(-1) 표시된 부분은 0으로 바꿔줌.
- 이외의 위치별로 좌, 상 방향의 숫자들을 더하며 끝까지 채운다.
- 가장 오른쪽 하단의 값(A[n][m])을 주어진 값(100,000,000,007)으로 나눈 나머지를 리턴한다.
파이썬 코드는 다음과 같다.
def solution(m, n, puddles):
A = [[0] * (m+1) for _ in range(n+1)]
A[1][1] = 1 # 시작 위치 표시
for pr, pc in puddles: # 물 웅덩이 표시
A[pc][pr] = -1
for r in range(1, n+1):
for c in range(1, m+1):
if (r, c) == (1, 1): # 시작 위치는 무시
continue
if A[r][c] == -1: # 물 웅덩이면 0으로 바꿔줌
A[r][c] = 0
else:
A[r][c] += (A[r-1][c] + A[r][c-1]) # 좌, 상 방향의 값을 더해줌
return A[n][m] % 1000000007
- 고찰 : 어렵지 않은 DP 문제였다! 더 더 많이 풀고 익숙해지자.
'Problem Solving > programmers' 카테고리의 다른 글
[Programmers] 수식 최대화(Python) / 2020 카카오 인턴십 (0) | 2021.05.08 |
---|---|
[Programmers] 정수 삼각형(Python) / Dynamic Programming (0) | 2021.05.03 |
[Programmers] 큰 수 만들기(Python) / Greedy (0) | 2021.02.26 |
[Programmers] SQL 고득점 Kit - JOIN (0) | 2021.02.26 |
[Programmers] SQL 고득점 Kit - String, Data (0) | 2021.02.26 |