[알고리즘/DP] 1932번 : 정수 삼각형 - python

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

1932번: 정수 삼각형

 

---

• 문제
• 소요시간: 15분 25초

---

• 설계하기(접근방법) 

1. 입력받기

삼각형 배열을 입력받는다

 

2. 구현하기

다음 항은

이전 항의 같은 열과

이전 행의 이전 열 중

최대값을 더하면 된다

 

dp[i][j] += max(dp[i -1][j - 1], dp[i - 1][j])

 

그리고 배열의 시작이나 끝일때만 예외처리를 해주면 된다

 

 

3. 출력하기

 

 

---

• 코드(출력)

n = int(input())

dp = [0 for _ in range(n)]

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

dp[1][0] += dp[0][0]
dp[1][1] += dp[0][0]

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

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

---

• 얻어갈 부분

1. 오랜만에 dp를 풀면서 감각을 익히고 있다. dp의 유형들을 잘 외워두자