[코딩테스트/프로그래머스/Python]등굣길

💡생각

다이나믹프로그래밍이니깐 재귀나 반복을 이용해야하고 고등학생때 배웠던 확통 방식으로 풀어야한다는건 알겠는데 도저히 풀 수가 없어서 다른 사람의 코드를 보았음.

⏬다른사람의 코드

나는 문제를 봤을 때 좌표가 반대인 것을 고려할 생각을 하지 못했고 왜 1000000007로 나눈 나머지값을 리턴해야하는지 이해하지 못함.

또, 아래 코드를 보고 dp를 초기화하는 과정의 코드가 잘 이해가 안돼서 그 부분을 공부 해야겠다고 생각함.

🔗풀이 참고
https://dev-note-97.tistory.com/141

def solution(m, n, puddles):
    puddles = [[q,p] for [p,q] in puddles]      # 미리 puddles 좌표 거꾸로
    dp = [[0] * (m + 1) for i in range(n + 1)]  # dp 초기화
    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:    # 웅덩이 위치의 경우 값을 0으로
                dp[i][j] = 0
            else:                    # 현재 칸은 왼쪽 칸, 위 칸의 합산!
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007
    return dp[n][m]

1. 문제에서의 좌표가 일반적인 좌표와 반대이므로 puddles 좌표 거꾸로 함.
2. dp: 결과 저장용 리스트.
   집에서 학교까지 가는 길인 m x n 크기만큼 리스트를 만들어줌.
3. dp[1][1]에 집의 위치 지정.
4. 이중 for문을 돌면서 웅덩이 위치의 경우에는 dp에 0을 저장, 그렇지 않을 경우에는 현재 칸의 왼쪽 칸과 위 칸에 저장된 값을 합산한 뒤 문제의 요구대로 1,000,000,007로 나눈 나머지 값을 저장함.
5. 마지막으로 dp[n][m]에 저장된 값을 return함.

🔗프로그래머스 - 등굣길
https://programmers.co.kr/learn/courses/30/lessons/42898