문제

https://school.programmers.co.kr/learn/courses/30/lessons/42898

풀이

시도 1

  • 2차원 테이블의 DP 문제로 점화식을 먼저 찾아야함
  • 점화식 : dp[x][y] = dp[x-1][y] + dp[x][y-1] > 현재좌표는 왼쪽좌표와 위의좌표의 합
  • index오류 가 생기지 않게 초기화 할때 집이 1,1부터 시작하고 왼쪽좌표와 위의좌표는 0으로 채워줌
  • 웅덩이가 발견되면 0으로 바까서 왼쪽값 + 위에값 = 위에값만 나올 수 있게 처리하면 된다.
solution.py 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


def solution(m, n, puddles):
    # 점화식 : dp[x][y] = dp[x-1][y] + dp[x][y-1]
    # dp 초기화, 1,1 부터 시작할거고 왼쪽과 위에값을 비교해야하므로 0으로 빈값을 초기화시켜줌
    dp = [[0] * (m+1) for i in range(n+1)]
    # 시작위치
    dp[1][1] = 1
    # 웅덩이는 -1
    for x, y in puddles:
        dp[y][x] = -1
    for x in range(1, n + 1):
        for y in range(1, m + 1):
            # 웅덩이면 0으로 바꿔서 다음값이 위에값이 될 수 있게
            if dp[x][y] == -1:
                dp[x][y] = 0
                continue
            # 점화식
            dp[x][y] += dp[x-1][y] + dp[x][y-1]
            # print(dp)

    return dp[n][m] % 1000000007

output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

[[0, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, -1, 0, 0], [0, 0, 0, 0, 0]]
[[0, 0, 0, 0, 0], [0, 1, 1, 0, 0], [0, 0, -1, 0, 0], [0, 0, 0, 0, 0]]
[[0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, -1, 0, 0], [0, 0, 0, 0, 0]]
[[0, 0, 0, 0, 0], [0, 1, 1, 1, 1], [0, 0, -1, 0, 0], [0, 0, 0, 0, 0]]
[[0, 0, 0, 0, 0], [0, 1, 1, 1, 1], [0, 1, -1, 0, 0], [0, 0, 0, 0, 0]]
[[0, 0, 0, 0, 0], [0, 1, 1, 1, 1], [0, 1, 0, 1, 0], [0, 0, 0, 0, 0]]
[[0, 0, 0, 0, 0], [0, 1, 1, 1, 1], [0, 1, 0, 1, 2], [0, 0, 0, 0, 0]]
[[0, 0, 0, 0, 0], [0, 1, 1, 1, 1], [0, 1, 0, 1, 2], [0, 1, 0, 0, 0]]
[[0, 0, 0, 0, 0], [0, 1, 1, 1, 1], [0, 1, 0, 1, 2], [0, 1, 1, 0, 0]]
[[0, 0, 0, 0, 0], [0, 1, 1, 1, 1], [0, 1, 0, 1, 2], [0, 1, 1, 2, 0]]
[[0, 0, 0, 0, 0], [0, 1, 1, 1, 1], [0, 1, 0, 1, 2], [0, 1, 1, 2, 4]]

다른사람풀이

solution.py 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def solution(m, n, puddles):
    answer = 0
    info = dict([((2, 1), 1), ((1, 2), 1)])
    for puddle in puddles:
        info[tuple(puddle)] = 0

    def func(m, n):
        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))
    return  func(m, n) % 1000000007