---

🔗 문제 링크

dp - 탑다운

(1,1)에서 오른쪽 혹은 아래쪽으로 1번씩 이동할 수 있을 때,
입력값(m,n)까지 이동하는 경우의 수를 모두 구하자.

---

문제풀이

풀이흐름

최종 목적지에 도달하기 위해서는,
최종 목적지 이전 중간 목적지들까지 오는 경우의 수를 먼저 알아야 한다.

재귀함수를 이용하면
점화식에 의해 각 위치의 경우의 수가 하향식으로 결정되며,
계산된 결과는 메모이제이션으로 저장한다.

메모제이션에 저장된 결과를 조합하면
최종 목적지까지 오는 전체 경우의 수를 구할 수 있다.

---

예시

최종 목적지: (2,2)

시작점 : (1, 1)

중간 목적지 : (1,2 / 2,1)

1,2 까지 경우의 수 : 1

2,1 까지 경우의 수 : 1

최종목적지까지 경우의수: 1 + 1 = 2

ex) 최종 목적지: (2,2)
시작점 : (1, 1)
중간 목적지 : (1,2 / 2,1)
1,2 까지 경우의 수 : 1
2,1 까지 경우의 수 : 1

최종목적지까지 경우의수: 1 + 1 = 2

점화식 : dp[i][j] = dp[i-1][j] + dp[i][j-1]

---

정답 코드

def solution(m, n, puddles):
    answer = 0  # (1,1)에서 (m,n)까지 이동하는 경우의 수

    # 시작점 (1,1)에서 한 번 이동한 두 칸의 경우의 수를 미리 초기값으로 설정.(점화식 적용을 위해)
    info = dict([((2, 1), 1), ((1, 2), 1)]) # 1,1로 시작하면  dp 점화식이 참조하는 값이 생기지 않아, 문제풀이를 할 수 없음.

    # # 웅덩이 좌표를 튜플로 변환하여 info 딕셔너리에 0으로 저장 (해당 위치로 갈 수 없음)
    for puddle in puddles: 
        info[tuple(puddle)] = 0 

    def func(m, n): # 탑다운(재귀+ 메모제이션) 방식으로 경우의 수 계산

        # 격자 밖이면 0 반환
        if m < 1 or n < 1:
            return 0

        # 이미 계산된 좌표면 바로 반환 (메모이제이션)
        if (m, n) in info:
            return info[(m, n)]

        # 현재 좌표 = 위에서 등교하는 경우 + 왼쪽에서 등교하는 경우
        return info.setdefault(
            (m, n),
            func(m - 1, n) + func(m, n - 1)
        )

    # 최종 결과는 MOD 적용
    return func(m, n) % 1000000007

---

다른 풀이

dp - 바텀업

def solution(m, n, puddles):
    answer = 0
    route_map = [[0]*m for i in range(n)]
    memo = [[0]*m for i in range(n)]
    for p in puddles:
        route_map[p[1]-1][p[0]-1] = 1
    memo[0][0] = 1
    for i in range(n):
        for j in range(m):
            if i == 0 and j == 0:
                continue
            if route_map[i][j] == 1:
                memo[i][j] = 0
            elif i == 0:
                memo[i][j] = memo[i][j-1]
            elif j == 0:
                memo[i][j] = memo[i-1][j]
            else:
                memo[i][j] = memo[i-1][j] + memo[i][j-1]
    print(memo)
    answer = memo[n-1][m-1]
    return answer % 1000000007```

---

생각해 본 것

다소 뻔한 말이지만,

DP 문제는 탑다운과 바텀업 두 방식 모두로 풀이가 가능하며,
상황에 따라 어떤 방식이 더 적합한지 고민해볼 필요가 있다.

찾아보니 일반적으로는 아래 기준으로 선택하면 좋다고 한다.

상황	추천 방식	이유
시간/메모리 제한이 타이트함	바텀업	함수 호출 오버헤드가 없고 반복문 기반이라 성능이 안정적임
모든 상태를 다 확인해야 함	바텀업	순차적으로 dp 테이블을 채우는 방식이 가장 효율적임
필요한 부분만 골라 계산하고 싶음	탑다운	재귀 + 메모이제이션으로 필요한 경로만 탐색 가능 (가지치기 효과)
점화식이 복잡해 순서 잡기 힘듦	탑다운	결과에서 거꾸로 호출하며 생각하면 구조 이해가 쉬움