[파이썬] 백준 1932 : 정수 삼각형

[파이썬] 백준 1932 : 정수 삼각형

1932번: 정수 삼각형

---

문제

---

풀이

0. 방향성 생각

딱 봐도 DP 문제.

 

1. 규칙 찾기

입력 받을 때에는 직각삼각형으로 들어와서 위에 행이 아래 행에 어떻게 영향주는지 파악을 해야한다.

맨 왼쪽, 맨 오른쪽 줄에는 계속 맨 왼쪽, 오른쪽의 합을 누적해준다.

가운데 끼어있는 경우에는 자신과 인덱스가 같거나, 하나 적은 인덱스에서 숫자가 내려온다.

이 때 둘 중 큰 숫자를 택하면 된다.

 

---

전체 코드

n = int(input())
arr = []
for i in range(n):
    arr.append(list(map(int,input().split())))

for h in range(1,n):
    for w in range(h+1):
        if w==0 :
            arr[h][0] += arr[h-1][0]
        elif w==h:
            arr[h][-1] += arr[h-1][-1]
        else :
            arr[h][w] += max(arr[h-1][w-1],arr[h-1][w])
print(max(arr[-1]))

DP치고는 크게 생각할거리가 없다. 가중치나 조건없는 계단오르기 정도의 문제