문제가 숫자의 합 중에 최대를 구하는 문제였다면 훨씬 쉽게 풀었을 것이다. 그러나 이 문제에서 중요한 점은 숫자의 합 중 최대값을 나타내는 경로의 수를 구하는 것이다.
이것을 해결하는데 시간이 많이 들었다.
일단 최대값을 나타내는 경로를 구하기 위해서는 먼저 최대값을 구하는것은 필수적이라고 생각이 들어 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)