정수삼각형 lv3

🌈문제 링크

★사전에 알아야 할 것

–> 피보나치 수열 & dp

ʕっ•ᴥ•ʔっ
dp를 잘 모르겠다면 이것 클릭 ㄱㄱ

풀이

def solution(triangle):

    for i in range(1, len(triangle)): # i = 몇번째 줄인지
        for j in range(i+1): # j = 줄 안에서 인덱스

            if j == 0: # 가장 왼쪽인 경우
                triangle[i][j] += triangle[i-1][j]

            elif j == i: # 가장 오른쪽인 경우
                triangle[i][j] += triangle[i-1][-1]

            else: # 가운데인 경우, (가장 왼쪽의 우측 것과 가장 우측의 좌측 것 비교)
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
                
    return max(triangle[-1])

풀이

• 삼각형의 각 위치 (i, j) —> i번째 행, j번째 열

for i in range(1, len(triangle)):

첫번째 행(0)은 그대로 두고, 두번째 행부터 시작해 각 위치 최대값 합 계산

i의 범위 —> 1 ≤ i ≤ len(triangle)-1

for j in range(i+1):

j(인덱스)는 열 구하는데 사용 —> 범위: i 까지

왼쪽 대각선 위에서 내려오는 경우

        `if j == 0: 
            triangle[i][j] += triangle[i-1][j]`

★ 쉽게 이해 —> 열(j)가 없으면 더 이상 왼쪽 아래로 못 내려가게 됩니다

당연히 없으니까 초기값 0 으로 설정

오른쪽 대각선 위에서 내려오는 경우

        `elif j == i: 
            triangle[i][j] += triangle[i-1][-1]`

가운데에서 내려갈 때

        `else: 
            triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])`

참고

https://soohyun6879.tistory.com/157

https://velog.io/@seulki971227/프로그래머스-Lv.3-정수-삼각형-Python