[알고리즘][백준] 1932번 정수 삼각형 - 파이썬(python) 풀이

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

1932번: 정수 삼각형

---

dp로 가장 유명한 문제가 아닌가 싶다!

 

처음 dp의 개념을 알기 위해 유튜브를 봤을때, 이 문제를 예시로 설명하는 영상을 봐서 문제를 보자마자 그 문제다! 이랬다

 

나의 아이디어는 가장자리는 그대로 내려와 더해지지만,

num[i][0] = num[i-1][0] + num[i][0]
num[i][-1] += num[i-1][-1] + num[i][-1]

 

중간에 있는 수는 두 가지 경우가 생겨 max로 더 큰 값만 저장해주어야 한다

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

import sys

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

num = []

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

for i in range(1, n):
    num[i][0] += num[i-1][0]
    num[i][-1] += num[i-1][-1]
    for j in range(1, i):
        num[i][j] += max(num[i-1][j-1], num[i-1][j])

print(max(num[-1]))

 

 

 

다른 분들의 코드를 리뷰해보니 나와 비슷하게 풀었는데

 

for문 안에 if문을 넣어 가장자리 부분을 해결한걸 볼 수 있었다!

 

시간은 내가 24ms정도 빠르게 나왔다

import sys

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

num = []
for _ in range(n):
    num.append(list(map(int, sys.stdin.readline().split())))

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

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

1932_정수삼각형.py

0.00MB