알리바바와 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에 채워 넣었다. (이렇게 하면 나처럼 조건문을 길게 쓰지 않아도 된다.)
Author And Source
이 문제에 관하여(알리바바와 40인의 도둑(Bottom-Up)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lsj8706/알리바바와-40인의-도둑Bottom-Up저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)