사용자 도구

사이트 도구


ps:problems:programmers:42898

등굣길

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호42898
문제명등굣길
레벨Level 3
분류

동적 계획법

시간복잡도O(nm)
인풋사이즈n<100, m<=100
사용한 언어Python
해결날짜2021/06/25
태그

고득점 Kit - 동적계획법

풀이

  • 전형적인 2차원 DP. puddle이 없다면 최단 경로의 수를 조합으로 바로 계산할 수 있지만, 이 경우는 DP로 풀어야 한다.
  • 어떤 좌표까지 가는 경로의 수는, 왼쪽에서 가는 경로의 수 + 위쪽에서 가는 경로의 수가 된다. 점화식은 dp[r][c] = dp[r-1][c] + dp[r][c-1] 이고, (r,c)가 puddle일때는 dp[r][c]=0 으로 처리하면 된다.
  • 총 시간복잡도는, n*m DP 테이블을 채우는 데에는 드는 O(nm).

코드

"""Solution code for "Programmers 42898. 등굣길".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42898
- Solution link: http://www.teferi.net/ps/problems/programmers/42898
"""

MOD = 1_000_000_007


def solution(m, n, puddles):
    puddles_set = {(r - 1, c - 1) for c, r in puddles}
    dp_cur = [1] + [0] * (m - 1)
    for r in range(n):
        dp_cur, dp_prev = [], dp_cur
        for c in range(m):
            if (r, c) in puddles_set:
                dp_cur.append(0)
            elif c == 0:
                dp_cur.append(dp_prev[c])
            else:
                dp_cur.append((dp_cur[-1] + dp_prev[c]) % MOD)
    return dp_cur[-1]

토론

댓글을 입력하세요:
D N G A A
 
ps/problems/programmers/42898.txt · 마지막으로 수정됨: 2021/06/29 13:16 저자 teferi