[Python Algorithm] 알고스팟 삼각형 위의 최대 경로 수 세기 - TRIPATHCNT

Chani·2022년 3월 11일
0

알고리즘

목록 보기
11/16
post-thumbnail


풀이 과정

문제가 숫자의 합 중에 최대를 구하는 문제였다면 훨씬 쉽게 풀었을 것이다. 그러나 이 문제에서 중요한 점은 숫자의 합 중 최대값을 나타내는 경로의 수를 구하는 것이다.
이것을 해결하는데 시간이 많이 들었다.

일단 최대값을 나타내는 경로를 구하기 위해서는 먼저 최대값을 구하는것은 필수적이라고 생각이 들어 tri배열을 돌며 각 경우에서의 최대값을 cost 배열에 저장해주었다.
tri배열의 0번째 인덱스와 마지막 인덱스인 경우 하나밖에 선택지가 없으므로 예외처리를 해주었고, 나머지 경우는 왼쪽 대각선 위쪽의 값과 바로 위쪽 값을 비교해서 cost 배열에 큰 값을 넣어주는 방식으로 구현하였다.

최대 경로의 개수를 구하기 위해 cnt배열을 따로 선언해주고 이 배열에 최대값의 경로의 숫자를 저장해주었다.
비교해주는 두 수가 다른 경우에는 경로가 하나밖에 없으므로 그대로 cnt 값을 옮겨 주었고, 두 수가 같은 경우에는 두 경로 모두 최대값의 경로이므로 두가지 cnt 값을 더해서 저장해주었다.

마지막에는 cost배열로부터 최대값을 얻어내주고, 이 값을 이용하여 cost값을 돌면서 구하고자 하는 최대 경로의 수를 구해주었다.


최종 코드

T = int(input())

for _ in range(T):
  n = int(input())
  tri = [list(map(int, input().strip().split(' '))) for _ in range(n)]
  cost = [[0 for _ in range(i + 1)] for i in range(n)]
  cnt = [[0 for _ in range(i + 1)] for i in range(n)]

  cost[0][0] = tri[0][0]
  cnt[0][0] = 1

  for i in range(1, n):
    for j in range(i + 1):
      if j == 0:
        cost[i][j] = tri[i][j] + cost[i - 1][j]
        cnt[i][j] = cnt[i - 1][j]
      elif j == i:
        cost[i][j] = tri[i][j] + cost[i - 1][j - 1]
        cnt[i][j] = cnt[i - 1][j - 1]
      else:
        if cost[i - 1][j - 1] > cost[i - 1][j]:
          cost[i][j] = cost[i - 1][j - 1] + tri[i][j]
          cnt[i][j] = cnt[i - 1][j - 1]
        elif cost[i - 1][j - 1] < cost[i - 1][j]:
          cost[i][j] = cost[i - 1][j] + tri[i][j]
          cnt[i][j] = cnt[i - 1][j]
        else:
          cost[i][j] = cost[i - 1][j] + tri[i][j]
          cnt[i][j] = cnt[i - 1][j] + cnt[i - 1][j - 1]
  max_val = max(cost[n - 1])
  ans = 0

  for i in range(n):
    if cost[n - 1][i] == max_val:
      ans += cnt[n - 1][i]
  print(ans)

결과

삼각형 위의 최대 경로 수 세기 문제 출처
GitHub 코드

profile
프론트엔드에 스며드는 중 🌊

0개의 댓글