[동적 계획법] 백준 1932번 정수 삼각형 (Python 파이썬)

💡문제 링크

https://www.acmicpc.net/problem/1932

 

💡문제 분석 요약

한 층에 하나의 숫자를 선택

선택한 모든 숫자의 합이 최대가 되는 그 최댓값을 출력

 

💡알고리즘 설계

1. n(층수) 입력받기

2. 테이블화를 하기 위해 (n+1)*(n+1) 크기의 테이블 만들기

 

3. 각 층의 숫자들을 테이블에 넣기

4. 아랫층의 숫자 중 가장 큰 수를 본인과 합한 수를 본인에게 넣기

알고리즘 흐름이 잘 이해가 안 될 때에는 직접 손으로 그려보기!

💡코드

n = int(input())

# 테이블화
table = [[0] * (n+1) for _ in range(n+1)]

# 테이블 채워넣기
for i in range(1, n+1):
  table[i][1:i+1] = list(map(int, input().split()))

# 최대값 채워넣기
for i in range(n-1, 0, -1):
  for j in range(1, i+1):
    table[i][j] += max(table[i+1][j], table[i+1][j+1])

print(table[1][1])

# 짧은 버전
n = int(input())
table = [[0] * (n+1) for _ in range(n+1)]
for i in range(1, n+1):
  table[i][1:i+1] = list(map(int, input().split()))
for i in range(n-1, 0, -1):
  for j in range(1, i+1):
    table[i][j] += max(table[i+1][j], table[i+1][j+1])
print(table[1][1])

💡 오답 풀이

테이블화를 하기 위해 (n+1)*(n+1) 크기의 테이블 만들기--에서 약간 애를 먹음 

table = [[0] * (n+1)] * (n+1) (X)
table = [[0] * (n + 1) for _ in range(n + 1)] (O)

위의 코드로 작성하면 곱셈으로 만들어진 리스트이기 때문에 하나의 요소가 변하면 다른 요소들도 변함.

반복을 위해 곱셈 말고 for문을 사용해야 한다

💡 다른 풀이

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]))

 

💡 느낀점 or 기억할정보

손으로 직접 써보니까 전체적인 그림이 한 눈에 파악된다.

아 이렇게 DP를 쓰면 문제가 쉽게 풀리는구나~를 처음으로 이해함

풀자마자 바로 맞았다!