[알고리즘]

이것이 코딩테스트다 #32

저번에 풀었던 #31과 비슷한 유형이어서 비슷하게 풀어봤다.

알고리즘

다이나믹 프로그래밍 보텀업 방식으로
(x,y)에 값이 (x-1,y) 또는 (x-1,y-1) 과 더해지는 경우가 있다고 생각했다.

그래서 dp[i-1][j],dp[i-1][j-1] 중에 최댓값을 dp[i]dp[j]에 더해주는 방식으로 풀었다

• (예외1) 마지막 열이라면 dp[i-1][j] 값이 존재하지 않는다.
• (예외2) 첫번째 열이라면 dp[i-1][j-1] 값이 존재하지 않는다.

n= int(input())
dp=[]
for _ in range(n):
    dp.append(list(map(int,input().split())))
for i in range(1,n):
    temt=0
    for j in range(len(dp[i])):
        if j==len(dp[i])-1:
            temt=dp[i-1][j-1]
        elif j==0:
            temt=dp[i-1][j]
        else:
            temt=max(dp[i-1][j],dp[i-1][j-1])
        dp[i][j]+=temt
print(max(dp[n-1]))

시간 복잡도

이중 for문 으로 O(n x n)->500 x 500->250000
시간 제한 2초
1초에 1억개정도 이므로 처리 가능!