[프로그래머스 | 파이썬 python] 등굣길

동적계획법 (Dynamic Programming) | DP

🌏 문제

프로그래머스

👽 첫 번째 풀이

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

고딩 때 경우의 수 문제 풀듯이 그림까지 그려가며 코드 짰는데 개같이 실패하였다.

 

 

👁 문제점 분석

가로-세로 1열을 1로 채워주었는데 이전에 물웅덩이가 나오면 앞으로 나아갈 수 없으므로

물웅덩이 이후는 0으로 처리해주어야 한다!

 

👁 반례

질문하기에 천사님이 남겨주신 반례덕분에 문제점을 발견할 수 있었다.

질문하기에 따봉박기가 없는게 너무 아쉽다 하 감사함다 사랑함다❤️

print(solution(2, 2, []), 2)
print(solution(3, 3, []), 6)
print(solution(3, 3, [[2, 2]]), 2)
print(solution(3, 3, [[2, 3]]), 3)
print(solution(3, 3, [[1, 3]]), 5)
print(solution(3, 3, [[1, 3], [3, 1]]), 4)
print(solution(3, 3, [[1, 3], [3, 1], [2, 3]]), 2)
print(solution(3, 3, [[1, 3], [3, 1], [2, 3], [2, 1]]), 1)
print(solution(7, 4, [[2, 1], [2, 2], [2, 3], [4, 2], [4, 3], [4, 4], [6, 2], [6, 3]]), 0) // 이 값이 잘 나오면 테스트1, 테스트9 통과, 위로 가면 안됨
print(solution(4, 4, [[3, 2], [2, 4]]), 7)
print(solution(100, 100, []), 690285631)

프로그래머스

 

👽 최종 코드

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

    for puddle in puddles:
        dp[puddle[1] - 1][puddle[0] - 1] = 0

    for i in range(1,m):
        if dp[0][i] == 0:
            for j in range(i, m):
                dp[0][j] = 0
            break
        dp[0][i] = 1

    for i in range(1, n):
        if dp[i][0] == 0:
            for j in range(i, n):
                dp[j][0] = 0
            break
        dp[i][0] = 1

    dp[0][0] = 0


    for i in range(n):
        for j in range(m):
            if dp[i][j] == -1:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    return dp[-1][-1] % 1000000007