Lv.3_등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898?language=python3

프로그래머스

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

 

다이나믹 프로그래밍 문제를 풀어봤다

이 유형의 문제는 처음 푸는 거라 어려움을 겪었다

 

DP (다이나믹 프로그래밍)은 어렵게 생각하지 말고 쉽게 '피보나치 수열'이라고 생각하면 될 것 같다

 

단순 재귀 형식으로 푸는 것이 아니라

-가장 먼저 메모 리스트에 저장되어 있는 값인지 확인

-만약 저장되어 있지 않다면 작은 사이즈로 하위 문제로 나누어 계산된 결과를 메모에 저장

-만약 저장되어 있다면 메모 값 반환

이 방식으로 계산을 수행한다

 

최적화 Optimization 문제는 대부분 DP로 문제를 해결한다는 것을 잊지 말자