백준 1932 정수 삼각형 python

백준 1932 정수 삼각형 Python2 구현

위에서 부터 아래로 가면서 최대합을 구한다면 경우의 수를 모두 구해 비교해보아야한다.

그렇기 때문에 반대로 가장 밑 노드 부터 최대 합을 계산해서 구해나가면 시간이 단축 될것이라는 생각하에 구현했다.

def code_1932():

        #input

        num = input()

        array = []

        for i in range( 0 , num ) :

                nums = raw_input()

                array.append(nums.split())

        #code

        for i in range(num-1 , 0, -1):

                if i == 0 :

                        break;

                for j in range (0, i):

                        if int(array[i][j]) > int(array[i][j+1]) :

                                array[i-1][j] = int(array[i-1][j]) + int(array[i][j])

                        else :

                                array[i-1][j] = int(array[i-1][j]) + int(array[i][j+1])

        print(array[0][0])

if __name__ == "__main__":

        code_1932()