[🥲 프로그래머스] 등굣길 - Dynamic programming

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

코딩테스트 연습 - 등굣길

 

✅ 내 풀이 (망!)

# 시간초과ㅜㅜ
def solution(m, n, puddles):
    to_house = []
    answer = []
    
    # 격자만큼의 배열 생성
    for i in range(n):
        to_house.append([True]*m)
            
    # 웅덩이 위치는 false로 변경 
    for puddle in puddles:
        x = puddle[0]-1
        y = puddle[1]-1
        to_house[x][y] = False
    
    answer = [[(0,0)]]
    for a in answer:
        temp = []
        for i in a:
            x = i[0]
            y = i[1]
            if x+1 < n:
                if to_house[x+1][y] != False:
                    temp.append((x+1,y))
            if y+1 < m:    
                if to_house[x][y+1] != False:
                    temp.append((x,y+1))
        answer.append(temp)

내가 생각한 알고리즘은

1) n*m 크기만큼의 리스트 생성 -> 웅덩이가 있는 인덱스에는 false로 표시

2) answer 리스트에서 하나씩 꺼내서 x좌표 +1, y좌표+1해서 각각 저장.....

그리고 리턴하려고 했는데 ㅜㅜ 시간 초과로 이 알고리즘 자체가 안통함!

 

✅ 다른 사람들 풀이

def solution(m, n, puddles):
    house = []
    
    # 격자만큼의 배열 생성 (인덱스 에러 방지로 위,옆 한줄씩 추가)
    for i in range(n+1):
        house.append([0]*(m+1))
    # 시작점 표시    
    house[1][1]=1
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            if i==1 and j==1: # 시작점일 경우 pass 
                continue
            if [j,i] in puddles: # 물 웅덩이일 경우 
                house[i][j] = 0
            else: # 나머지는 위, 왼쪽 값 합쳐서 저장
                house[i][j]=house[i-1][j]+house[i][j-1]
                
    return house[n][m]%1000000007

def solution(m,n,puddles):
    grid = [[0]*(m+1) for i in range(n+1)] #왼쪽, 위로 한줄씩 만들어서 IndexError 방지
    
    if puddles != [[]]:                    #물이 잠긴 지역이 0일 수 있음
        for a, b in puddles:
            grid[b][a] = -1    #미리 -1로 체크
            
    grid[1][1] = 1
    
    for j in range(1,n+1):
        for k in range(1,m+1):
            if j == k == 1:                #(1,1)은 1로 만들어두고, 0이 되지 않도록
                continue
            if grid[j][k] == -1:           #웅덩이는 0으로 만들어 다음 덧셈 때 영향끼치지 않게
                grid[j][k] = 0
                continue
            grid[j][k] = (grid[j][k-1] + grid[j-1][k])%1000000007   #[a,b] = [a-1,b] + [a,b-1] 공식

    return grid[n][m]

 

 

이 정도면 수학공부부터 해야하는 게 아닐까...