[백준/파이썬] 1932번 정수 삼각형 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1932번 정수 삼각형
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

정수 삼각형에서 꼭대기부터 아래로 내려오며 인접한 칸으로만 이동할 때 얻을 수 있는 합의 최댓값을 구하는 문제입니다.

코드

n = int(input())

t = []

for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(i+1 if i > 0 else 0):
        tmp[j] += max(t[i-1][j-1] if j > 0 else 0, t[i-1][j] if j < i else 0)
    t.append(tmp)

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

설명

각 위치의 값에 이전 줄에서 올 수 있는 두 경로 중 큰 값을 더해 누적합니다.

마지막 줄에서 최댓값이 전체 최대 경로 합입니다.

---

• 백준 문제풀이 전체 목록 보기

---