[백준 1932번] 정수 삼각형 (Python/파이썬)

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

1932번: 정수 삼각형

어제 포스팅 했던 RGB거리 문제와 상당히 비슷한 문제이다.

다이나믹 프로그래밍을 이용하는 문제로 삼각형 위에서부터 최대가 되도록 내려와야한다.

잘못하면 큰수만 따라가면 되는거 아닌가? 라고 생각할 수 있는데 작은 수로 내려가다가 도중에 압도적으로 큰수가 나오면 그 경로가 가장 큰 경우가 되기 때문에 큰수만 따라가면 안된다.

결국 다 해봐야 한다는 뜻이다. 

Dp == memoization + bruteforce 따라서 완전탐색도 포함되어 있기 때문에 문제를 풀때 DP를 사용해야할거 같다면      어느정도 노가다할 각오도 해야한다.

 

풀이는 삼각형의 변에 있는 수들은 그냥 그대로 위에서부터 따라 내려오는 경우의 수 밖에 없기 때문에 그냥 내려오면 되고, 내부에 있는 수들은 위의 두 수들 중에서 큰 수를 골라서 내려오면 된다.

여기서 위에 있는 수들은 삼각형에 있는 수들이 아니라 그 수에 도달할때 만들어질 수 있는 가장 큰 수 이다.

(위에서 하나씩 합하면서 내려온 합 삼각형에서 배열에서 큰수를 고른다는 뜻이다, 코드에서는 maximum배열에 해당한다.)

내부를 어떻게 구하는지 이해가 안간다면 코드를 백준 예제를 적용하여 한번 손으로 따라 해보면 이해할 수 있을 것이다.

코드는 다음과 같다.

 

import sys
input = sys.stdin.readline
triangle = []
n = int(input())

##삼각형 배열 생성
for _ in range(n):
  triangle.append(list(map(int,input().split())))
  
##삼각형 합 배열 생성
maximum = []
for i in range(1, n+1):
  maximum.append([-1 for _ in range(i)])
maximum[0][0] = triangle[0][0]

##DP
for i in range(1, n):
  for j in range(i+1):
    if (j-1 > -1) and (j < i):
      maximum[i][j] = max(maximum[i-1][j-1],maximum[i-1][j]) + triangle[i][j]
    elif j >= i:
      maximum[i][j] = maximum[i-1][j-1] + triangle[i][j]
    elif j-1 <= -1:
      maximum[i][j] = maximum[i-1][j] + triangle[i][j]
print(max(maximum[n-1]))

 

 

 

 

RGB거리하고 문제가 거의 비슷해서 힘들지 않고 거의 바로 푼거같다.

한번 틀렸는데 삼각형 변하고 내부를 구분하는 조건식을 안하고 try-catch문으로 하려고 하다가 틀렸다.