백준 파이썬 1932번 정수 삼각형

🚀접근하기

<다이나믹 프로그래밍>

일단 첫째줄부터 차근차근 시작했다. 그림과 같이 dp[1]일 경우와, dp[2]일 경우를 일단 적어보았는데, dp[2]인 경우부터 max값을 사용해서 윗줄 중 더 큰 수를 선택해서 더해야 했다. 모든 경우를 다 max로 하면 indexError가 나기 때문에 어떻게 해야 할까 하다가 아예 경우를 3가지로 나눠야한다는 것을 깨달았다.

dp[i][j]라고 한다면 먼저 1) j==0인 경우 2) j==(len(dp[i])) (그림에선 n이라고 표현함) 3)그 외의 경우 이렇게 3가지의 경우로 나누어주었다.

 

이런식으로 계속해서 윗줄부터 수를 더해준 후에, 마지막에 가장 마지막 줄 중에서 가장 큰 수를 출력해주면 된다. 

🎉코드

N = int(input())

dp=[]

for i in range(N):
    dp.append(list(map(int, input().split())))

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

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

1) if j == 0인 경우, 2) if j == len(dp[i])-1인 경우, 3)else 그 외의 경우로 나누어주었고, 

반복문을 통해 계속 윗줄부터 차례대로 수를 더해준 후에, 마지막에 print(max(dp[N-1]))를 통해 마지막 줄 중에서 가장 큰 수를 출력해주었다.

💪다짐

다이나믹 프로그래밍 문제는 풀수록 재밌는 거 같다. 무턱대고 코드부터 작성할 것이 아니라 일단 문제를 손으로 써보면서 규칙을 찾는 것이 다이나믹 프로그래밍의 가장 중요한 부분인 것 같다. 

몇 문제 더 풀어보면서 완전히 마스터해야겠다!