1주차_백준(2) - 정수 삼각형

▶문제

 

 

 

▶풀이

n=int(input())
d=[]
for i in range(n):
  d.append(list(map(int, input().split())))

for i in range(1,n):
  for j in range(len(d[i])):
    if j==0:
      d[i][j]=d[i][j]+d[i-1][j]
    elif j==len(d[i])-1: 
      d[i][j]=d[i][j]+d[i-1][j-1]
    else:
      d[i][j]=max(d[i-1][j-1],d[i-1][j])+d[i][j]
print(max(d[n-1]))

 

• 삼각형의 각 요소는 두 개의 바로 위 요소 중 더 큰 값에 현재 요소의 값을 더한 것
• 각 요소에 대해 최대 경로합을 계산하기 위해 DP 테이블을 설정
• 삼각형을 위에서 아래로 내려가면서 각 위치의 최대 경로합을 업데이트하여 가장 마지막 줄에서 최댓값을 찾으면 전체 경로에서의 최대 합을 구할 수 있음

n = int(input())
d = []
for i in range(n):
    d.append(list(map(int, input().split())))

 

 

삼각형의 행 수를 입력받아 d에 저장한다. 그 후 map 함수를 이용해 정수형으로 변환한다.

for i in range(1, n):
    for j in range(len(d[i])):
        if j == 0:
            d[i][j] = d[i][j] + d[i-1][j]
        elif j == len(d[i]) - 1:
            d[i][j] = d[i][j] + d[i-1][j-1]
        else:
            d[i][j] = max(d[i-1][j-1], d[i-1][j]) + d[i][j]

삼각형의 각 행을 처리하면서, 현재 위치의 값을 업데이트한다. 각 요소는 위쪽 요소 중 적절한 값을 선택하여 더해 최대 경로합을 구한다.

print(max(d[n-1]))

삼각형의 마지막 행에서 가장 큰 값을 찾아 출력한다.