[프로그래머스] 동적계획법 3. 등굣길

문제

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

코딩테스트 연습 - 등굣길

 

---

풀이

1. 전체를 -1로 초기화
2. puddles 를 0으로 만든다.
3. 첫번째 행부터 순회하며 각 경우의 수를 저장한다.

def solution(m, n, puddles):
    grid = [[-1] * m for _ in range(n)]
    
    if m > 0: # (1,0) (0,1) 초기화
        grid[1][0] = 1
    if n > 0:
        grid[0][1] = 1
        
    for i, j in puddles: #웅덩이를 지나는 것은 불가
        grid[j-1][i-1] = 0

    for i in range(n):
        for j in range(m):
            if grid[i][j] != -1 or i + j == 0: #웅덩이와 집은 계산하지 않음
                continue
            if i == 0:
                grid[i][j] = grid[i][j-1]
            if j == 0:
                grid[i][j] = grid[i-1][j]
            if i != 0 and j != 0: #위쪽과 왼쪽의 경우의 수를 합
                grid[i][j] = grid[i-1][j] + grid[i][j-1]

    return grid[n-1][m-1] % 1000000007

로직은 쉽게 떠올랐는데 예외처리에서 조금 시간을 썼다.

그리고 웅덩이 좌표가 (m,n)인데 처음에 (n,m)으로 잘못 계산해서 고치는데 시간이 좀 걸렸다..

문제를 잘 읽자.

시간복잡도는 O(n*m)이다.

 

---

다른 사람의 풀이

def solution(m,n,puddles):
    grid = [[0]*(m+1) for i in range(n+1)] #왼쪽, 위로 한줄씩 만들어서 IndexError 방지
    if puddles != [[]]:                    #물이 잠긴 지역이 0일 수 있음
        for a, b in puddles:
            grid[b][a] = -1                #미리 -1로 체크
    grid[1][1] = 1
    for j in range(1,n+1):
        for k in range(1,m+1):
            if j == k == 1:                #(1,1)은 1로 만들어두고, 0이 되지 않도록
                continue
            if grid[j][k] == -1:           #웅덩이는 0으로 만들어 다음 덧셈 때 영향끼치지 않게
                grid[j][k] = 0
                continue
            grid[j][k] = (grid[j][k-1] + grid[j-1][k])%1000000007   #[a,b] = [a-1,b] + [a,b-1] 공식

    return grid[n][m]

로직 자체는 비슷하다.