[백준1932&파이썬] DP를 이용할때 확정지을 노드를 선택하는 기준과 근거가 필요하다.

# 문제

백준 1932 정수 삼각형 파이썬 풀이

1932번: 정수 삼각형

# 코드

import sys

n = int(sys.stdin.readline().strip())

arr = list()
for _ in range(n) :
  line = list(map(int,sys.stdin.readline().split()))
  arr.append(line)

for row in range(1,n):
  for col in range(len(arr[row])) :
    if col == 0 : # 시작점이면
      arr[row][col] += arr[row-1][col]
      continue
    if col == len(arr[row])-1 : # 끝점이면
      arr[row][col] += arr[row-1][col-1]
      continue
    # 그 외 경우인 경우
    arr[row][col] += max(arr[row-1][col], arr[row-1][col-1])

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

# 풀이

• 먼저 문제에서 주어진 정수 삼각형의 틀가 실제 배열로 들어오는 정수 삼각형의 모양이 다르다는 것을 알고, 이 두개가 똑같이 맵핑시킬 수 있는지에 대한 관계를 찾았다.
• 생각보다 쉽게 바로 아래와 오른쪽 대각선 아래가 쉽게 매핑 됐다. 현재 보는 노드에서 바로 아래와 오른쪽 대각선을 보게 되는 규칙을 가진다.
• 문제 해결 전략은 현재 노드에서 살펴보는 위의 노드를 비교해보고 현재 자신의 값과 더했을때 최대가 되는 값으로 자신을 확정짓는 방법의 DP를 이용하면 된다.
• DP의 중요점은 현재 확정지어야하는 노드를 선택하는 방법이고 그 노드를 선택했을때 이후 선택에 영향을 주지 않는 근거가 있어야한다.

• 다음과 같이 위의 노드를 보게 되는 경우 col(열)이 0번인 경우의 맨끝인 경우는 양쪽을 보지 않고 바로 위 또는 대각선 위만을 보게 된다. 이걸 반복문에서 표현해야 했다.

    if col == 0 : # 시작점이면
      arr[row][col] += arr[row-1][col]
      continue
    if col == len(arr[row])-1 : # 끝점이면
      arr[row][col] += arr[row-1][col-1]
      continue