[코딩테스트] 프로그래머스 - 정수 삼각형

1. 아이디어

▪ 비용 리스트 0으로 초기화, 가장 처음 값은 삼각형의 꼭대기 값으로 초기화

▪ 2중 for 문 돌면서 해당 위치 기준으로 오른쪽 아래, 왼쪽 아래 값 비용 값 갱신 

   - 현재 저장된 비용 값과 현재 위치에서 해당 위치로 가는 경로값을 비교한 후에 큰 값으로 갱신 

▪ 비용 리스트의 가장 마지막 행의 최대값 return 

2. 시간복잡도

▪ O(N^2)

3. 변수

▪ 거리 비용 리스트: int[][]

Code

def solution(triangle):
    rs = []
    for ls in triangle:
        rs.append([0] * len(ls))
    rs[0][0] = triangle[0][0]

    for j in range(len(triangle)-1):
        for i in range(len(triangle[j])):
            rs[j + 1][i] = max(rs[j][i] + triangle[j + 1][i], rs[j + 1][i])
            rs[j + 1][i + 1] = max(rs[j][i] + triangle[j + 1][i + 1], rs[j + 1][i + 1])

    answer = max(rs[-1])
    return answer

 

프로그래머스