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

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

1932번: 정수 삼각형

 

문제

정수 삼각형에서 위에서부터 아래로 내려오면서 최댓값을 구할 수 있는 경로를 찾아 최댓값을 구하면 되는 문제다.

 

문제를 보고 인덱싱을 어떻게 할지 고민했다.

 

				0
			1		2
		3		4		5
	6		7		8		9
10		11		12		13		14

이렇게 인덱스를 처리하자니,, 규칙성을 못찾아서 포기하고 새로운 방법을 생각해 냈다.

 

				0
			0		1
		0		1		2
	0		1		2		3
0		1		2		3		4

이렇게 인덱스를 부여하면 쉽게 인덱싱을 할 수 있다.

 

2차원 리스트로 정리하면 이렇게 정리할 수 있다.

				arr[0][0]
			arr[1][0]		arr[1][1]
		arr[2][0]		arr[2][1]		arr[2][2]
	arr[3][0]		arr[3][1]		arr[3][2]		arr[3][3]
arr[4][0]		arr[4][1]		arr[4][2]		arr[4][3]		arr[4][4]

 

문제를 풀기 위해서 나는 https://codingjoa.tistory.com/entry/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC1149-RGB%EA%B1%B0%EB%A6%AC

[백준/파이썬]1149 RGB거리

이때 푼 문제랑 비슷하게 풀었다.

 

 

				arr[0][0]
		arr[0][0]+arr[1][0]			arr[0][0]+arr[1][1]
arr[0][0]+arr[1][0]+arr[2][0]			max(arr[0][0]+arr[1][0]+arr[2][1], arr[0][0]+arr[1][1]+arr[2][1])			arr[0][0]+arr[1][1]+arr[2][2]

이런 식으로 진행해 주면 되는데 이런 식으로 진행하기 위해서는 아래의 3가지 경우로 나눠서 각각 계산해 주면 된다.

1. 오른쪽 사이드

2. 왼쪽 사이드

3. 중간

 

1. 오른쪽 사이드

오른쪽 사이드의 경우는 arr[i][j]에서 j == len(arr[i])-1인 경우이다.

 

1. 왼쪽 사이드

왼쪽 사이드일 경우는 간단하다. arr[i][j]일때, j == 0일 경우이다.

 

2. 중간

위 두 가지 경우가 아닌 경우이다.

 

이 경우들을 생각한 후 문제를 풀면 쉽게 풀 수 있다.

 

정답

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(len(arr[i])) :
        if len(arr[i])-1 == j :
            arr[i][j] += arr[i-1][len(arr[i-1])-1]
        elif j == 0 :
            arr[i][j] += arr[i-1][0]
        else :
            arr[i][j] += max(arr[i-1][j-1], arr[i-1][j])

print(max(arr[-1]))