[Baekjoon]백준 1932 정수 삼각형(실버 1) - Python

문제설명

문제를 살펴보면 이번에는 이전 문제에서 삼각형으로 바뀐 조건이다

단계별로 풀어보기에서 앞선 문제들을 풀어왔다면 어렵지 않게 해결가능하다

하나의 리스트를 만들어 삼각형의 값들을 저장해주고, 부분합을 이용하여 마지막 줄에 합을 저장하면 된다

 

for문을 두개 만들어 바깥쪽 for문은 행을 가리키도록, 안쪽 for문은 열을 가리키도록 변수를 설정한다

이후에 첫번째 열이라면 대각선 왼쪽으로 이동할 index가 없기 때문에 오른쪽 index의 값과 더해준다

마지막 열이라면 반대로 대각선 오른쪽으로 이동할 index가 없기 때문에 왼쪽 index의 값과 더해주면 된다

그리고 그 중앙에 위치한 열들은 두 대각선의 index의 값 중에서 더 큰 값을 더해 값을 저장해주면 된다

조금 헷갈릴수는 있지만 그림을 그려가며 이해하다보면 더 쉽게 할 수 있다

그리고 마지막 행에서 가장 큰 값을 출력해주면 코드는 완성이다

N = int(input())
triangle = []

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