[Python] 파이썬 프로그래머스 등굣길

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

프로그래머스

---

나의 풀이

• 아래와 오른쪽으로만 이동 가능
• 물 웅덩이는 지나가지 못함

 

• 빨 -> 파 -> 초 -> 검 방향으로 갈 수 있는 경우의 수를 체크함

• 여기서 puddles이 x, y 정렬이 아니라 y, x 정렬이라 반대로 넣어줘야 함
  • 이거 때문에 시간이 오래 걸림

def solution(m, n, puddles):
    roadmap = [[0]*(m+1) for j in range(n+1)]
    roadmap[1][1] = 1
    for pud in puddles:
        roadmap[pud[1]][pud[0]] = -1

    for y in range(1, m+1):
        for x in range(1, n+1):
            if roadmap[x][y] == -1:
                roadmap[x][y] = 0
            else:
                roadmap[x][y] += roadmap[x-1][y] + roadmap[x][y-1]
    return roadmap[n][m]

효율성에서 실패가 떠서 다시 문제를 읽어보니 %1000000007을 빼먹었다.

def solution(m, n, puddles):
    roadmap = [[0]*(m+1) for j in range(n+1)]

    for pud in puddles:
        roadmap[pud[1]][pud[0]] = -1

    for y in range(1, m+1):
        for x in range(1, n+1):
            if x == 1 and y == 1:
                roadmap[x][y] = 1
            elif roadmap[x][y] == -1:
                roadmap[x][y] = 0
            else:
                roadmap[x][y] = roadmap[x-1][y] + roadmap[x][y-1]
    return roadmap[n][m] % 1000000007