[프로그래머스] 등굣길

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

2차원 배열의 각 칸별로 도착할 수 있는 경우의 수를 저장하였습니다.

2차원 배열의 누적합을 구하는 방법과 유사하게 접근하였습니다.

2) 알고리즘

• DP
• 누적합

3) 풀이 코드

사용 언어 - Python

def solution(m, n, puddles):
    dp = [[0] * (m+1) for _ in range(n+1)]              # 2차원 배열 생성, 누적합과 유사하여 가장 왼쪽 열과 가장 위의 행을 0으로 모두 채움

    dp[0][1] = 1                                        # 출발지 (1, 1) 에 도착 가능한 경우의 수를 1개로 만들기 위함
    for i in range(1, n+1):                             # 2차원 배열 반복
        for j in range(1, m+1):
            if [j ,i] in puddles:                       # 현재 좌표가 물에 잠긴 경우, 이 곳으로 이동이 불가능하므로 0 으로 설정
                dp[i][j] = 0
            else:                                       # 현재 좌표에 도착 가능한 경우의 수는
                dp[i][j] = dp[i-1][j] + dp[i][j-1]      # 왼쪽에서 현재 위치로 오는 경우의 수 + 위에서 현재 위치로 오는 경우의 수

    return dp[n][m] % 1000000007                        # 반환

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

코딩테스트 연습 - 등굣길

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다