[BOJ] #1932. 정수삼각형 (Python) (DP)

📖Problem

1932번: 정수 삼각형

1932번: 정수 삼각형

🔍Institution

1. 어떻게 동작 과정이 수행되는지 핸드트레이싱해본다.
2. 리스트를 어떻게 받아낼지 아이디어를 떠올린다.

이 2가지 과정을 거쳤다.

1. 어떻게 동작 과정이 수행되는지 핸드트레이싱해본다.이때, 양쪽 끝에 있는 부분은 그냥 그대로 내려받는다.그게 아니라면, max()를 이용해서 양쪽으로 내려오는 것들 중 더했을 때 더 큰 값을 다시 저장하도록 한다.
   ⇒ 대각선 왼쪽, 대각선 오른쪽만 이동할 수 있다.
2. 리스트를 어떻게 받아낼 것인가?가장 간단한 방법은 중첩 리스트를 이용하는 것이다.

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

---

중첩리스트를 다시 한 번 살펴보자

[[7],
[3, 8], 
[8, 1, 0], 
[2, 7, 4, 4], 
[4, 5, 2, 6, 5]]

이렇게 된 상태에서 동작과정을 살펴보도록 한다. 이때 2차원 리스트이기 때문에 2중 for문이 불가피하다. 또한, 문제의 제한사항에서도 2초, 최대범위 500이기에 2중 for문을 사용해도 문제가 없음을 확인하였다.

바깥 for문의 인덱스는 i로, 안쪽 for문의 인덱스는 j라고 하였을 때

• j의 값이 0인 7, 3, 8, 2, 4의 경우는 같은 위치에 있는 값을 그대로 내려받는다.
• j의 값이 i의 값과 같아질 때에는 j-1 위치에 있는 값을 그대로 누적해서 더한다.
• 그게 아닐 경우에는 현재 위치(j)에 있는 값과 이전 값(j-1)에 있는 값 중 더했을 때 더 큰 값이 되는 값으로 누적하여 더한다. (max() 이용)

🔍Approach

1. 입력받기

n = int(input())
arr = []

for i in range(n):
    temp = list(map(int, input().split()))
    arr.append(temp)
print(arr)

결과:

# 입력
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
# 출력
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

2. DP 처리

• 바깥 for문의 인덱스는 i로, 안쪽 for문의 인덱스는 j라고 하였을 때
• j의 값이 0인 7, 3, 8, 2, 4의 경우는 같은 위치에 있는 값을 그대로 내려받는다.
• j 값이 i의 값과 같아질 때에는 j-1 위치에 있는 값을 그대로 누적해서 더한다.
• 그게 아닐 경우에는 현재 위치(j)에 있는 값과 이전 값(j-1)에 있는 값 중 더했을 때 더 큰 값이 되는 값으로 누적하여 더한다. (max() 이용)

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

🚩My submission

import sys
input = sys.stdin.readline

# 입력값 저장
n = int(input())
arr = []
for i in range(n):
    temp = list(map(int, input().split()))
    arr.append(temp)

# DP 처리
for i in range(1, n):
    for j in range(0, i+1):
        if j == 0:
            arr[i][j] += arr[i-1][j]
        elif j == i:
            arr[i][j] += arr[i-1][j-1]
        else:
            arr[i][j] += max(arr[i-1][j], arr[i-1][j-1])
# 최대 합
print(max(arr[n-1]))

🚩Others submission

💡TIL

• dp 재밌다.