[programmers] 프로그래머스 Level3 등굣길(파이썬 Python)

(주)그렙

 

[programmers] 프로그래머스 Level3 등굣길

(파이썬 Python)

 

* 문제출처 : 프로그래머스 코딩 테스트 연습, 알고리즘 문제

 

 

 

1) 문제

---

코딩테스트 연습 - 등굣길

 

 

 

 

 

2) 코드

---

def is_puddle(m, n, puddles) :
    for puddle in puddles :
        puddle_m = puddle[0]
        puddle_n = puddle[1]
        
        if (m == puddle_m) and (n == puddle_n) :
            return True
    
    return False
 
def solution(m, n, puddles):
    array = [[0] * 110 for i in range(110)]
    
    array[1][1] = 1
 
    for i in range(1, m + 1) :
        for j in range(1, n + 1) :
            if (is_puddle(i, j, puddles) == True) :
                array[j][i] = 0
            else :
                array[j][i] = (array[j - 1][i] + array[j][i - 1] + array[j][i]) % 1000000007
            
    return array[n][m]

 

 

 

 

 

 

 

3) 풀이 과정

---

1) Dp로 풀어야겠다는 감이 온다.(Dp문제이기 때문에 Dp로 푼다 X)

 

    판단 근거?) 이전 길들의 최단경로의 합을 바탕으로 최종 도착지 까지의 최단경로의 합을 구한다.

 

	1	1	1	1
	1	0	1	2
	1	1	2	4

 

2) 배열의 크기를 넉넉히 +10 까지 잡아준다.

 

    1<= m,n <= 100 이기 때문에 110으로 넉넉히 설정

 

 

 

 

 

4) 정리 노트

---

* Dp(Dynamic Programming)

-> "부분의 정답을 가지고 점진적으로 전체 정답을 구하는 방법"

 

* 파이썬에서 2차원 배열 설정 방법?

    1) [0] * n for i in range(n)

    2) Numpy