[프로그래머스 lv 3] 등굣길

사용 언어 - Python3

문제 - 등굣길

프로그래머스

 

 

 

정답

DP 규칙 찾기 (정답 맞춘 여부 X) 

0. input

puddles <= n,m으로 바꿔주기

0으로 채워진 n*m 리스트 dq 생성

dq[1][1] = 1 첫 시작점은 1로 채워주기

 

2. dq 진행

오른쪽 아래로만 이동하기 때문에, 두가지 경우가 있다.

같은 행 왼쪽에서 오는 경우 & 윗 행에서 내려오는 경우

2.1. 예외처리

[1,1]은 지나가기 continue

만약 지나가는 길에 puddles이 있다면 0으로 만든다.

2.2. 현재까지 값을 더해주면서 경로 이동

가장 마지막 도착했을 때 값 return

def solution(m, n, puddles):
    answer = 0
    puddles = [[q,p] for [p,q] in puddles]
    dq = [[0]*(m+1) for _ in range(n+1)]
    dq[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:
                dq[i][j] = 0
            else:
                dq[i][j] = (dq[i][j-1] + dq[i-1][j]) % 1000000007

    return dq[n][m]

 

 

 

 

레퍼런스

• 정답 풀이

[프로그래머스] 등굣길 / Python

• 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부