[programmers python] 43105 정수삼각형

 

https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 

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

 

 

<problem>

 

 

 

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

 

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

 

 

<constraints>

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

 

---

 

<example>

 

 

↓

↓

↓

↓

↓

 

---

 

<solution ①>

 

1) 삼각형 테두리는 비교할 필요 없이 위의 값과 더하면 됨

    - triangle[i][0], triangle[i][len(triangle[i])-1]

2) 안쪽의 경우, 왼쪽 위의 값, 오른쪽 위의 값과 더한 것 중 더 큰 값을 저장

 

마지막 열에서 가장 큰 값을 return

 

---

 

ⓒ ⓞ ⓓ ⓔ

def solution(triangle):
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            if j == 0:
                triangle[i][j] += triangle[i-1][0]
            elif j == len(triangle[i])-1:
                triangle[i][j] += triangle[i-1][len(triangle[i-1])-1]
            else:
                a = triangle[i][j] + triangle[i-1][j-1]
                b = triangle[i][j] + triangle[i-1][j]
                triangle[i][j] = max(a, b)
    
    return max(triangle[i])

 

ⓣ ⓔ ⓢ ⓣ

 

---

len(triangle[i])-1 를 계속 구할 필요 없이 i번째 줄은 i가 0부터 시작할 때,  i+1개만큼 있음을 확인

그렇다면 i열의 마지막 값을 확인할 때에는 j가 결국 i+1-1이므로 j==1을 확인하면 된다. 

이 부분 코드 수정

 

---

 

ⓒ ⓞ ⓓ ⓔ

def solution(triangle):
    for i in range(1, len(triangle)):
        for j in range(i+1):
            if j == 0:
                triangle[i][j] += triangle[i-1][0]
            elif j == i:
                triangle[i][j] += triangle[i-1][i-1]
            else:
                a = triangle[i][j] + triangle[i-1][j-1]
                b = triangle[i][j] + triangle[i-1][j]
                triangle[i][j] = max(a, b)
    
    return max(triangle[i])

 

ⓣ ⓔ ⓢ ⓣ

 

---

 

ⓕ ⓘ ⓝ ⓐ ⓛ    ⓒ ⓞ ⓓ ⓔ

 

def solution(triangle):
    for i in range(1, len(triangle)):
        for j in range(i+1):
            if j == 0:
                triangle[i][j] += triangle[i-1][0]
            elif j == i:
                triangle[i][j] += triangle[i-1][i-1]
            else:
                a = triangle[i][j] + triangle[i-1][j-1]
                b = triangle[i][j] + triangle[i-1][j]
                triangle[i][j] = max(a, b)
    
    return max(triangle[i])