프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코드
def solution(m, n, puddles):
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
if i == 1 and j == 1:
dp[i][j] = 1
continue
if [j, i] not in puddles: # 물에 잠긴 지역이 아니라면
dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007
else: # 물에 잠긴 지역이라면
dp[i][j] = 0
return dp[n][m]
맞게 한 거 같은데 자꾸 틀리길래 뭔가 하고 봤더니 문제에서 물이 잠긴 지역의 좌표를 줄 때 행, 열 순서가 아닌 열, 행 순서로 주고 있었다...문제를 잘 읽고 풀도록 하자...
오른쪽과 아래쪽으로만 움직일 수 있기 때문에 어떤 칸으로 최단거리로 갈 수 있는 방법은 그 칸의 위 칸까지 최단거리로 가는 방법과 왼쪽 칸까지 최단거리로 가는 방법의 합이다. 수식으로 알기 쉽게 나타내면 아래와 같다.
dp[i][j] = dp[i-1][j] + dp[i][j-1]
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 10870번 피보나치 수 5 (0) | 2023.02.09 |
---|---|
[Python/파이썬] 프로그래머스 멀리 뛰기 (0) | 2022.11.04 |
[Python/파이썬] 프로그래머스 피보나치 수 (0) | 2022.10.20 |
[Python/파이썬] Summer/Winter Coding(~2018) 스티커 모으기(2) (0) | 2022.10.12 |
[Python/파이썬] 프로그래머스 정수 삼각형 (0) | 2022.10.10 |