title: "[프로그래머스] 등굣길 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/42898"
description: "프로그래머스 Level 3 문제 [등굣길]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

import sys; sys.setrecursionlimit(100000)
cache = {(0, 0): 1}

def solve(r, c, R, C, puddles):
    if (r, c) in cache:
        return cache[(r, c)]
    
    # 왼쪽 아니면 위쪽에서 옵니다.
    # 단, puddle이 아니어야 합니다.
    v = 0
    for dr, dc in [(-1, 0), (0, -1)]:
        if (r+dr, c+dc) not in puddles and 0 <= r+dr < R and 0 <= c+dc < C:
            v += solve(r+dr, c+dc, R, C, puddles)
    
    cache[(r, c)] = v % 1000000007
    return cache[(r, c)]

def solution(m, n, puddles):
    # DP로 해결
    puddles = set((r-1, c-1) for c, r in puddles)
    return solve(n-1, m-1, n, m, puddles)

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges