알리바바와 40인의 도둑(Bottom-Up)

생성일: 2022년 2월 24일 오후 3:26

구현 코드

# 알리바바와 40인의 도둑(Bottom-Up)
import sys
sys.stdin = open("input.txt", "rt")

n = int(input())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

dy = [[0 for _ in range(n)] for _ in range(n)]

for i in range(0, n):
    for j in range(0, n):
        if 0<=i-1<n or 0<=j-1<n:
            if 0<=i-1<n and 0<=j-1<n:
                top = dy[i-1][j]
                left = dy[i][j-1]
                if top <= left:
                    dy[i][j] = top + board[i][j]
                else:
                    dy[i][j] = left + board[i][j]
            elif 0<=i-1<n:
                top = dy[i-1][j]
                dy[i][j] = top + board[i][j]
            else:
                left = dy[i][j-1]
                dy[i][j] = left + board[i][j]
        else:
            dy[i][j] = board[i][j]

print(dy[n-1][n-1])

모범 답안

import sys
sys.stdin = open("input.txt", 'r')    
if __name__=="__main__":
    n=int(input())
    arr=[list(map(int, input().split())) for _ in range(n)]
    dy=[[0]*n for _ in range(n)]
    dy[0][0]=arr[0][0]
    for i in range(1, n):
        dy[0][i]=dy[0][i-1]+arr[0][i]
        dy[i][0]=dy[i-1][0]+arr[i][0]
    for i in range(1, n):
        for j in range(1, n):
            dy[i][j]=min(dy[i-1][j], dy[i][j-1])+arr[i][j]
    print(dy[n-1][n-1])

차이점

• 기본적인 로직은 같다.
• 각 칸을 반복문을 통해 돌면서 자신의 위와 왼쪽을 비교하고 그 중에서 작은값과 자신의 값을 더한 것을 dy에 담는다.
• 모범 답안에서는 우선 0번째 행과 열을 전부 먼저 dy에 채워 넣었다. (이렇게 하면 나처럼 조건문을 길게 쓰지 않아도 된다.)