[python] 백준 1932번: 정수 삼각형

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

분류

DP(다이나믹 프로그래밍)

 

C+ 코드 링크

choichumji.tistory.com/42

[C++][알고리즘] 프로그래머스:: 정수 삼각형

 

삼각형의 위 꼭짓점으로부터 아래의 왼쪽과 오른쪽으로 흘러내려가면서, 가장 합이 높은 경로를 찾아야 한다.

경로찾기 문제라 옛날엔 DFS나 BFS로 접근하려 했지만 그건 함정이다. 삼각형 크기가 최대 500 이므로 이런 알고리즘에서는 반드시 시간 초과가 되게 된다.

 

그래서 값을 기억하는 DP 방식을 사용해야 한다. 이 문제를 프로그래머스에서 접했을 때는 DP 개념을 잘 몰라 DFS 로 풀었는데, 다시 이문제를 파이썬으로 풀어보니 바로 기억이 나서 풀었다.

 

역시 사람이 같아서 그런가, 언어는 달라도 푸는 방식은 똑같네

 

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

dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = triangle[0][0]
for row in range(1, n):
    for col in range(len(triangle[row])):
        if col == 0:
            dp[row][col] = dp[row - 1][col] + triangle[row][col]
        elif col == len(triangle[row]) - 1:
            dp[row][col] = dp[row - 1][col-1] + triangle[row][col]
        else:
            dp[row][col] = triangle[row][col] + max(dp[row - 1][col - 1], dp[row - 1][col])

print(sorted(dp[n - 1],reverse=True)[0])

 

마지막 단에서, 역순 정렬을 통해서 첫번째 값을 가져왔는데, 더 좋은 방법이 있다.

max(iterable) 을 이용하면 단순했다.

 

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

알던 거 같으면서도 이런 디테일을 까먹는게 나인 것 같다 ㅠ