백준 알고리즘 1932 [파이썬]

배운 내용

이 문제는 동적 계획법(DP)를 사용해서 풀어야 하는 문제이다. 동적 계획법으로 문제를 풀어봤지만 이번 문제를 통해서 동적 계획법이 무엇인지 정확하게 이해할 수 있었다. 

동적 계획법 (Dynamic Programming)

동적 계획법은 재귀적으로 함수가 계속 실행될 때 소요 시간을 줄여주기 위해서 새로운 문제 값을 저장하고 해당 문제값이 저장되어있으면 다시 계산해서 그 값을 얻어내는게 아니라 미리 저장해두었던 값을 사용함으로써 재귀적으로 함수가 실행되는 시간을 대폭 줄여준다. 

 

동적 계획법에도 여러가지 방법이 있는것으로 알고 있는데, 이 문제에서는 기존 값에다가 필요한 값을 덧붙이면서 저장한다.

 

 

 

문제 

 

문제풀이

from sys import stdin
read = stdin.readline
lst = []
N = int(read())
for _ in range(N):
  # 각 줄마다 입력하는 숫자들을 리스트형식으로 만들고
  # 순서에 맞게 리스트들은 lst(리스트)안에 넣는다.
  lst.append(list(map(int, read().split())))
# lst안에 있는 리스트들을 차례대로 하나씩 꺼낸다.
# 하지만 2번째 리스트부터 꺼내기때문에 range(1, N)로 설정한다.
for i in range(1, N):
  # 그다음 for loop은 각각 리스트안에 있는 숫자들을 불러온다.
  for j in range(len(lst[i])):
    # 값을 더하는 경우의 수가 3개있다.
    if j == 0: #i번째 리스트의 index가 0일 때 i-1번째 리스트 index 0인 값과 더하면 된다.
      lst[i][j] += lst[i-1][j]
    elif j == len(lst[i])-1: #i번째 리스트의 마지막 숫자값은 i-1번째 리스트의 마지막 숫자값이랑 더하면 된다.
      # j가 -1이 될 수 없기 때문에 리스트 길이에 -1을 한다.
      lst[i][j] += lst[i-1][j-1]
    else: #리스트 중간에 있는 값들은 연결되있는 그전 리스트 두개 값중에 큰것과 더하면 된다.
      lst[i][j] += max(lst[i-1][j-1], lst[i-1][j]) 
print(max(lst[N-1]))