정수 삼각형 풀이

문제 링크: https://www.acmicpc.net/problem/1932

백준 알고리즘 기초 1/2 401에서 7번째 - 1932번 정수 삼각형을 풀어보았다.

 

풀이: 삼각형에서 원소의 위치를 왼쪽 변, 오른쪽 변, 둘 다 아닌 상태 이렇게 세 가지로 분류해야 한다.

 

C++

 

Python

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

Java