[알고리즘] 백준 1932 : 정수 삼각형 - S1

2023.05.26 풀이

import sys
input=sys.stdin.readline

s=[]
d=[]*(500)

n=int(input())
s.append(int(input()))
for _ in range(n-1):
    s.append(list(map(int, input().split())))

if n==1:
    print(s[0])
else:
    d.append(s[0])
    d.append([d[0]+s[1][0], d[0]+s[1][1]])

    res=[]*n
    for i in range(2, n):
        res.append(d[i-1][0]+s[i][0])
        for j in range(1, i):
            res.append(max(d[i-1][j-1], d[i-1][j])+s[i][j])
        res.append(d[i-1][-1]+s[i][i])
        d.append(res)
        res=[]
    print(max(d[n-1]))

• 가장 왼쪽은 왼쪽, 가장 오른쪽은 오른쪽끼리 합해나가고,
  그 사이 값들은 대각선 위의 두개 중 큰 값과 본인 값의 합
• 아이디어 캐치는 쉬웠는데 구현이 어려웠고 지저분

---

다른 풀이

 = int(input())
t = []
for i in range(n):
    t.append(list(map(int, input().split())))
k = 2
for i in range(1, n):
    for j in range(k):
        if j == 0:
            t[i][j] = t[i][j] + t[i - 1][j]
        elif i == j:
            t[i][j] = t[i][j] + t[i - 1][j - 1]
        else:
            t[i][j] = max(t[i - 1][j - 1], t[i - 1][j]) + t[i][j]
    k += 1
print(max(t[n - 1]))

# 1932  정수 삼각형 (파이썬 Python)
n = int(input())
dp = []

for i in range(n) :                            ## 입력값 이차원리스트 형태로 dp테이블에 저장하기
    dp.append(list(map(int,input().split())))

print(dp)
print(dp[1][0])

for i in range(1,n) :                           ## 행을 기준으로 for문 구성
    for j in range(0,i+1) :                     ## 열을 기준으로 for문 구성
        if j == 0 :
            dp[i][0] += dp[i-1][0]              # 0열끼리 더하기
        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]))                 # n-1행에서의 최댓값 출력

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

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

• 셋 다 비슷한 풀이

---

check point

• 굳이 dp 테이블을 또 만들 필요없이 주어진 리스트를 초기화하면서 풀어도 괜찮을 듯,, (ex. 윗 단계에서 += 하는 풀이)