[백준 1932] 정수 삼각형(python)

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

1932번: 정수 삼각형

정수 삼각형 문제

동적 프로그래밍을 활용해 가지고 푸는 문제다.

사실상 점화식? 패턴? 같은걸 생각만 해내면 쉽게 풀릴 수 있는 문제인데 생각보다 과정이 쉽지 않은거 같다

100% 내 생각으로 풀었는가?
--> O

어렵지 않게 접근할 수 있는 문제였기 때문에 3가지로만 잘 나눠서 계산하면 쉽게 해결할 수 있었고, 동적 프로그래밍 문제 중에 그나마.. 자력으로 해결할 수 있는 선의 문제였던거 같다. (다른 문제 보면 풀이는 간단한데 해결하는 거 생각해낸 분들 굉장히 리스펙!)

 

정답 코드

import sys
n = int(input())
x = [0]*n
for w in range(n):
    x[w] = list(map(int, sys.stdin.readline().split()))

for i in range(1, n):
    for j in range(len(x[i])):
        if j == 0: # 삼각형의 왼쪽 계산
            x[i][j] += x[i-1][j]
        elif j == len(x[i])-1: #삼각형의 오른쪽줄 계산
            x[i][j] += x[i-1][j-1]
        elif j < len(x[i-1]): # 삼각형의 내부 계산
            x[i][j] += max(x[i-1][j], x[i-1][j-1])
print(max(x[n-1]))

이번엔 깔끔하게 시간초과에 걸리지 않고 해결할 수 있었다. 왼쪽 / 가운데 / 오른쪽으로 나눠주는 것만 빠르게 캐치하면 쉽게 해결할 수 있던 문제

---

느낀점

다이나믹 프로그래밍 문제를 접근하면서 자꾸 경우의 수를 나눠서 하는 습관이 생겨서 비슷하게 시도해보니 생각보다 간단하게 풀렸던 문제! 근데 풀다가 범위 지정하다가 i랑 j값 하나씩 바꿔가면서 찾아내는 부분에서 시간을 조금 많이 소비했다. 그래도 문제 해결!😏