백준 1932번 <정수 삼각형>

백준 알고리즘 1932번

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

1932번: 정수 삼각형

---

1932번

입력으로 첫 줄에 삼각형의 크기 N이 주어지고 그 다음 N개의 줄에 걸쳐 정수 삼각형의 정보가 주어진다.

 

출력으로는 삼각형의 맨 위에서 맨 아래층으로 내려오는 경로에 있는 수의 합이 최대를 구해서 출력한다.

---

문제 해결

이 문제는 다이나믹 프로그래밍을 이용하여 풀 수 있다.

입력으로 들어오는 정수 삼각형을 triangle이라는 2차원 배열에 저장했다.

그러고 triangle 배열에 각 경로에 있는 수의 합을 메모제이션했다. -> 그림 1

그림 1

 

triangle 배열을 update하는 과정을 봐보자.

- 각 층의 양 끝은 해당 층의 위에 있는 부모(?)를 더해주면 된다.

  1) 왼쪽 끝은 triangle[i][j] += triangle[i-1][j]  (j는 0이다.)

  2) 오른쪽 끝은 triangle[i][j] += triangle[i-1][j-1] (윗 층의 맨 끝 숫자를 더하는 것)

- 양 끝이 아니라 중간인 부분은 윗 층의 왼쪽, 오른쪽 값 중 큰 값을 더해준다.

  이때 traingle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j]) 이다.

 

이 식에 맞춰서 코딩을 하면 된다.

---

코드

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

---

결과

---