문제설명

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

• 입력
  첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
• 출력
  첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

접근

이제까지 선택된 수의 합이 최대가 되는 경로를 구하는
매번의 선택에 따라 특정 위치에서의 누적값이 달라지고 이는 바로 직전의 누적값의 영향을 받음 => 큰 문제(이제까지 선택된 수의 최대합)를 작은 문제(바로 직전의 수의 최대합)로 나눌 수 있음
특정 지점의 최댓값은 다음 지점의 최댓값에 영향을 줌 => 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일함
점화식
dp[i][j] = array[i][j] + max(dp[i-1][j-1], dp[i-1][j])

풀이

# 내 풀이
n = int(input())
array = []
for _ in range(n):
  line = list(map(int, input().split()))
  array.append(line)

dp = [[0]*(x+1) for x in range(n)]
dp[0][0] = array[0][0]
for i in range(1, n):
  for j in range(i + 1):
    if j == 0:
      dp[i][j] = array[i][j] + dp[i - 1][j]
      continue
    elif j == i:
      dp[i][j] = array[i][j] + dp[i - 1][j - 1]
      continue
    else: 
      # 왼쪽 대각선에서 오는 경우  
      left_diag = dp[i - 1][j - 1]    
      # 오른쪽 대각선에서 오는 경우
      right_diag = dp[i - 1][j]
    dp[i][j] = array[i][j] + max(left_diag, right_diag)
print(max(dp[-1]))

# 책 풀이
n = int(input())

data = []

for i in range(n):
    data_list = list(map(int, input().split()))
    for j in range (n, i + 1, -1):
        data_list.append(0)
    data.append(data_list)

for i in range(n):
    for j in range(n):
        # 위에서 오는 경우
        if i == 0:
            up =  0
        else:
            up = data[i-1][j]
        # 왼쪽 위에서 오는 경우
        if i == 0:
            left_up = 0
        else:
            left_up = data[i-1][j-1]
        data[i][j] = data[i][j] + max(up, left_up)

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

배운점

• 리스트 표현식을 이용하여 2차원 배열을 초기화할 수 있음

dp = [[0]*(x+1) for x in range(n)]

• 구현 편의상 초기 데이터를 담는 array 변수를 사용하지 않고, 바로 dp 테이블에 초기 데이터를 담은 후 점화식에 따라 dp 테이블을 갱신할 수 있음