백준(baekjoon) 1932번: 정수 삼각형(실버 1, 파이썬 PYTHON) - 동적 계획법 1

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

 

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

import sys

n=int(sys.stdin.readline())
triangle=[]

for _ in range(n):
  line=list(map(int,sys.stdin.readline().split()))
  triangle.append(line)

for x in range(1,n):
  for y in range(len(triangle[x])):
    if(y==0):
      triangle[x][y]=triangle[x-1][y]+triangle[x][y]
    elif(y==len(triangle[x])-1):
      triangle[x][y]=triangle[x-1][y-1]+triangle[x][y]
    else:
      triangle[x][y]=max(triangle[x-1][y-1]+triangle[x][y],triangle[x-1][y]+triangle[x][y])

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

 

※ 동적 계획법 1

 

 

● 먼저 n을 입력 받은 후, triangle 라는 빈 배열을 하나 정의해준다. 그 후 들어오는 입력들을 배열에 저장한 뒤 그 배열을 triangle 에 차례대로 append 해준다. 

 

● 변수 x는 1부터 n-1 까지 돌고, 그 안의 변수 y는 0부터 triangle[x] 가 가리키는 배열의 길이-1 까지 돈다. triangle 배열안의 배열 각각의 요소들의 값은 각 단계마다 차례대로 그 순간의 최대 합으로 갱신될 예정이다.

 

case 1: y 의 값이 0일 때

-> triangle[x][y] 가 포함되는 최종 경로의 합은 이전 줄의 triangle[x-1][y] 에 저장되어 있는 값과 아직 갱신되지 않은 triangle[x][y] 의 값을 더해준 값이 되므로 이 값을 triangle[x][y] 에 넣어준다.

 

case 2: y 의 값이 triangle[x] 가 가리키는 배열의 길이-1 일 때

-> triangle[x][y] 가 포함되는 최종 경로의 합은 이전 줄의 triangle[x-1][y-1] 에 저장되어 있는 값과 아직 갱신되지 않은 triangle[x][y] 의 값을 더해준 값이 되므로 이 값을 triangle[x][y] 에 넣어준다.

 

case 3: y 의 값이 0과 triangle[x] 가 가리키는 배열의 길이-1 사이일 때

-> triangle[x][y] 가 포함되는 최종 경로의 합은 이전 줄의 triangle[x-1][y-1] 에 저장되어 있는 값과 아직 갱신되지 않은 triangle[x][y] 의 값을 더해준 값, 이전 줄의 triangle[x-1][y] 에 저장되어 있는 값과 아직 갱신되지 않은 triangle[x][y] 의 값을 더해준 값 중 더 큰 값이므로 더 큰 값을 triangle[x][y] 에 넣어준다.

 

● triangle 배열의 맨 끝에 저장되어 있는 배열에는 이제 각 요소의 값이 최종 경로 합에 포함 될 경우의 최대 합이 저장되어 있으므로 max(triangle[n-1]) 을 출력하면 답을 구할 수 있다.

 

 

결과