정수 삼각형 with Python

문제 출처: https://www.programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

동적계획법(Dynamic Programming) 정수 삼각형 (Level 3)

 

1. 알고리즘

• 두번째 줄 부터 한 줄씩 내려가며 위의 대각선 방향 두 수 중 큰 수를 더한다.
  • 1번 줄부터(0번 줄 제외) N-1줄까지 반복 / r
  • 각 줄의 숫자 갯수만큼 반복 / c
  • 가장 앞의 숫자일 경우(0번 인덱스의 수), 윗 줄의 가장 앞의 숫자를 더함
  • 가장 뒤의 숫자일 경우(len(triangle[r])-1번 인덱스), 윗 줄의 가장 뒤의 숫자를 더함
  • 윗 줄의 한 칸 앞의 인덱스(c-1), 동일 인덱스(c) 중 큰 수를 자기 자신과 더함
• 가장 아랫 줄의 수 중 최댓값을 answer로 반환

 

2. 유의 사항

 

3. 어려웠던 점, 해결방법

 

4. 소스 코드

상세 코드 설명은 주석

def solution(triangle):
    
    #두번째 줄 부터 끝까지
    for r in range(1, len(triangle)):
        #각 줄의 숫자 갯수만큼
        for c in range(len(triangle[r])):
            #가장 앞의 숫자
            if c == 0:
                triangle[r][c] += triangle[r-1][0]
            #가장 뒤의 숫자
            elif c == len(triangle[r])-1:
                triangle[r][c] += triangle[r-1][-1]
            #그 외, 대각선 한 칸 오른쪽, 왼쪽의 수 중 큰 수를 더함
            else:
                triangle[r][c] += max(triangle[r-1][c-1], triangle[r-1][c])
    
    #가장 아랫 줄의 최댓값
    answer = max(triangle[-1])
    return answer

5. 고민

• 아래에서 위로 올라가며 연산했다면,,, 마지막에 max를 찾는 연산을 안해도 되지 않았을까,,,? max함수의 시간복잡도가 n인데 줄일 수 있었을 것같다.