[BOJ] 1932 정수 삼각형_DP

정수 삼각형

link

풀이

• 방식 : DP

📰code

n = int(input())

dp = [[0] for i in range(n+1)]
for i in range(n):
    dp[i].append(0)
    temp = list(map(int,input().split()))
    for j in range(len(temp)):
        dp[i+1].append(max(dp[i][j]+temp[j],dp[i][j+1]+temp[j]))
print(max(dp[n]))

다른 풀이

• zip 함수를 사용하여 inline for문을 사용하여 속도가 더 빠름

📰code

  import sys
  n = int(input())
  triangle =[]
  for _ in range(n):
      triangle.append(list(map(int, sys.stdin.readline().rstrip().split())))
                  
  accum = []
  for i in range(n):
      accum = [max(a+c, b+c) for a,b,c in zip([0]+accum, accum+[0], triangle[i])]
  print(max(accum))

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡