BOJ 1932: 정수 삼각형

다이내믹 프로그래밍 문제는 정말 많다....ㅠ

문제가 많은 만큼, 만들어 낼 수 있는 점화식도 정말 다양하고, 문제의 종류도 정말 많다.

그런 만큼, 더욱 열심히 문제를 풀어야겠다는 생각이 든다.

BOJ 1932: 정수 삼각형

 

 

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

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

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

해당 문제에 대한 내 코드다.

우선, 삼각형을 입력받고, 

각 층에 대해서 dp를 돌린다.

만약 삼각형의 맨 왼쪽 끝이거나 오른쪽 끝이면, (j==0 or j==i)

바로 위에 있는 값에서 더해주면 되겠다.

만약 그렇지 않다면, dp에서 위에 있는 두 값에서 큰 값을 가져오면 되겠다.

 

쉽게 생각하면 무엇보다 쉽고, 어렵게 생각하면 무엇보다 어려운 듯 하다.