백준 1932번 (dp활용)

 

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

1932번: 정수 삼각형

문제

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

예시:

                           7

                    3+7  8+7

              8+10   1+15   0+15

      2+18    7+18    4+16    4+15

4+20    5+25    2+25    6+20    5+19

좌측 첫열들은 위에 바로 위에 있는 열의 합과 더해지고

우측 첫열들은 좌측 위에 있는 열의 합과 더해지고

나머지 열들은 위와 좌측의 합 중 큰 수를 더해준다.

코드:

import sys
n = int(sys.stdin.readline())
dp = [0]*n # n행개의 배열생성


for i in range(n):
    dp[i]=list(map(int,sys.stdin.readline().split()))#각행마다 열==list를 넣어줌
for i in range(1,n): #2번째열부터 시작
    for j in range(i+1):
        if j==0:#각행의 첫번째열일경우
            dp[i][j]+=dp[i-1][j]#바로 위의 합을 더해줌
        elif j==i:#각행의 마지막 열일경우
            dp[i][j]+=dp[i-1][j-1]#좌측 위의 합을 더해줌
        else:#각행의 가운데 열들일경우
            dp[i][j]+=max(dp[i-1][j],dp[i-1][j-1])#바로 위의 합과 좌측위의 합중 큰것을 더해줌
        
print(max(dp[n-1])) #맨마지막 행에서 가장 큰수 print