131. 1932(정수 삼각형)

import sys
input = sys.stdin.readline

N = int(input())
triangle = [list(map(int,input().split())) for _ in range(N)]

sum = 0
result = []

for i in range(1,N):
  for j in range(0,i+1):
    if(i == 1):
      triangle[i][j] += triangle[0][0]
      continue
    
    if(j == 0):
      triangle[i][j] += triangle[i-1][0]
      continue
    
    if(j == i):
      triangle[i][j] += triangle[i-1][j-1]
      continue
     
    triangle[i][j] += max(triangle[i-1][j-1],triangle[i-1][j]) 

print(max(triangle[N-1]))

문제요약

N층 까지 있는 정수 삼각형에 값을 주는데 아래층으로 내려올 때 선택된 수의 합이 최대인 경우를 구하라.

설명

다음과 같이 차례로 누적합을 구해 나가면서 최종에 도달 했을 때 최대 값을 고르면 된다.

if(i == 1):
      triangle[i][j] += triangle[0][0]
      continue

 

두번째 케이스 부터 시작하는데 맨 처음( 3과 8이 나오는 부분)에는 전에 값이 하나밖에 없으므로 그 값을 바로 더한다.

if(j == 0):
      triangle[i][j] += triangle[i-1][0]
      continue

현재 테스트 케이스의 인덱스가 0인 값은 무조건 전 케이스의 인덱스가 0인 값을 더해야 한다.

if(j == i):
      triangle[i][j] += triangle[i-1][j-1]
      continue

현재 테스트 케이스의 인덱스가 마지막인 값은 무조건 전 케이스의 인덱스의 마지막 값을 더해야 한다.

    triangle[i][j] += max(triangle[i-1][j-1],triangle[i-1][j])

위에 모두 해당 되지 않는 경우 전 케이스 두 값 중 최대값을 찾아서 그 값을 더하고 덮어 씌우면 된다.