[프로그래머스] 등굣길

처음에는 조합? 확률과 통계 공식으로 풀어보려했는데 생각해보니 그렇게 복잡하게 풀 필요가 없었다.

테두리를 1로 초기화하고 puddle이 있는 좌표는 0으로 하여

dp[i][j]=dp[i-1][j]+dp[i][j-1]

을 사용해 풀면 되는 것이었다!

 

def solution(m, n, puddles):
    dp=[[1]*n for _ in range(m)]
    for p in puddles:
        dp[p[0]-1][p[1]-1]=0
            
    for i in range(1,m):
        for j in range(1,n):
            if dp[i][j]!=0:
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007
                
    return dp[m-1][n-1]

처음에는 puddle 위치를 0으로 만들고 dp 적용하면 되겠다 싶었는데 두세개의 테스트케이스에서 실패가 떴다.

 

 

이유는 puddle이 테두리에 있는 경우를 고려하지 않았기 때문이었다.

테두리에 puddle이 있는 경우 그 이후의 테두리도 0으로 초기화 해주어야한다.

def solution(m, n, puddles):
    dp=[[1]*n for _ in range(m)]
    for p in puddles:
        dp[p[0]-1][p[1]-1]=0

    for i in range(m):
        if dp[i][0]==0:
            for t in range(i,m):
                dp[t][0]=0
            break
    for j in range(n):
        if dp[0][j]==0:
            for t in range(j,n):
                dp[0][t]=0
            break
            
    for i in range(1,m):
        for j in range(1,n):
            if dp[i][j]!=0:
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007
                
    return dp[m-1][n-1]

 

적용해주면 성공!