[Silver I] 정수 삼각형 - 1932

문제 링크

성능 요약

메모리: 35616 KB, 시간: 148 ms

분류

다이나믹 프로그래밍

문제 설명

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

---

🔧 알고리즘

각 줄에서 첫번째와 마지막에 위치한 수는 대각선이 하나 밖에 존재하지 않는다. 각 줄의 첫번째에 위치한 수는 항상 윗 줄의 첫번째 수만 가져올 수 있고, 각 줄의 마지막에 위치한 수는 항상 윗 줄의 마지막 수만 가져올 수 있다. 그리고 그 사이에 위치한 수는 양 대각선에 위치한 수들 중에 더 큰 값을 가져와서 값을 저장한다. 이렇게 계속 값을 업데이트 한다.

코드 설명

• 2차원 리스트로 입력 받은 수를 저장한다.

  N = int(input())
  
  triangle = []
  
  for k in range(N) :
      triangle.append(list(map(int, input().split()))) # 2차원 리스트로 저장한다.

• 주요 알고리즘

  for j in range(1, N) :
      triangle[j][0] += triangle[j-1][0] 
      triangle[j][len(triangle[j]) - 1] += triangle[j-1][len(triangle[j]) - 2] 
      for i in range(1, len(triangle[j]) - 1) :
          triangle[j][i] += max(triangle[j-1][i-1], triangle[j-1][i])

  시작은 두번째 줄부터 시작한다. 첫번째에 위치한 수는 바로 윗줄의 첫번째 줄의 첫번째 수를 더해준다. 그리고 마지막에 위치한 수는 현재 줄의 길이를 구하고, 마지막 위치한 수는 그 윗줄의 마지막 위치한 수를 더해준다.
  👉 여기서 궁금한 것이 있을 수 있다. 왜 마지막 위치한 수를 -2를 한 것이 궁금할 것이다. 그 이유는 윗줄의 리스트 길이는 현재의 리스트 길이보다 1이 적기 때문이다.
  이 과정이 끝났으면 이제 그 사이의 숫자들을 구해주는 것이다. 여기에 알고리즘은 간단하다. 양쪽 대각선의 위치한 수들 중 더 큰 max 값을 가져와서 더해주는 것이다. 최종적으로는 마지막 줄 리스트에서 max 값을 찾아주면 되는 것이다.

• 업데이트 된 삼각형
  

---

📁 코드

깃허브

🧷 이미지 출처

https://www.acmicpc.net/