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

 

 

접근법

- 결과를 도출해 내기 위해서는 삼각형의 맨 밑에 있는 수들의 각 값을 알아야겠다고 생각했다. 각 값들을 구하려면 값으 좌상 혹은 우상 중 더 큰 값을 자신의 값과 더해야한다. 그렇기 때문에 삼각형의 모든 노드에서 최선의 값을 구하려고 했다.

 

- 일단 좌변과 우변은 고를 것 없이 자신의 상위 노드(좌변일 경우 triangle[i - 1][j], 우변일 경우 triangle[i - 1][j - 1])와 자신을 더한 값이 최선의 값이다.

 

- 그 외의 경우 자신을 기준으로 좌상의 값과 우상의 값 중 더 큰 값을 자신과 더하고 이 값을 triangle[i][j]에 저장한다.

 

- 맨 밑 변에서 max값을 출력한다.

 

 

 

 

 

 

풀이

N = int(input())
triangle = list()
for _ in range(N) :
    triangle.append(list(map(int, input().split())))
    
for i in range(1, len(triangle)) :
    for j in range(len(triangle[i])) :
        if j == 0 :
            triangle[i][j] += triangle[i - 1][j]
        elif j == len(triangle[i]) - 1 :
            triangle[i][j] += triangle[i - 1][j - 1]
        else :
            triangle[i][j] += max(triangle[i - 1][j], triangle[i - 1][j - 1])

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

 

 

 

 

 

 

 

결과