99클럽 코테 스터디 40일차 TIL, 프로그래머스 / 등굣길

🔑 오늘의 학습 키워드 DP

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/42898#

 

def solution(m, n, puddles):
    grid = [[0] * (m+1) for _ in range (n+1)]
    
    for x,y in puddles:
        grid[y][x] = -1
        
    for i in range (1,n+1):
        for j in range (1,m+1):
            if i == 1 and j == 1:
                grid[1][1] = 1
            elif grid[i][j] == -1:
                grid[i][j] = 0
            else:
                grid[i][j] = grid[i-1][j] + grid[i][j-1]

    return grid[n][m] % 1000000007

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

웅덩이라는 제약 조건을 갖고 있는 dp 문제

⏰ 예상 시간 복잡도 O(N * M)

제한사항
격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
물에 잠긴 지역은 0개 이상 10개 이하입니다.
집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

 

😎 알고리즘 개요

해당 지점에 도착하는 것을 생각해봐야 한다.

 

1,1 에서 출발해서 2, 3에 도착하려면

출발 0	1	1
1	2	도착 3

 

1,1 -> 1,2 -> 1,3 -> 2,3

 

1,1 -> 1,2 -> 2,2 -> 2,3

 

1,1, -> 2,1 -> 2,2 -> 2,3

 

이렇게 3개가 있는데 각 격자에 도착할 수 있는 경우의 수를 더해나가면 된다.

 

물웅덩이는 갈 수 없으니 0으로 두면 된다.

 

✅ 오늘의 회고

- 딥 히 ~ :)

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL