[BOJ] 1932 정수삼각형 Python

N = int(input())
A = []
for i in range (0,N):
    a = list(map(int,input().split()))
    A.append(a)

def f(n):
    if n == 0:
        return A[0][0]
    else:
        for i in range (1,n):
            for j in range (0,len(A[i])):
                if j == 0:
                    A[i][j] += A[i-1][j]
                elif j == len(A[i-1]):
                    A[i][j] += A[i-1][j-1]
                else:
                    a = A[i][j] + A[i-1][j-1]
                    b = A[i][j] + A[i-1][j]
                    A[i][j] = max(a,b)
        ans = max(A[n-1])
        return ans
print(f(N))

 

먼저, 삼각형의 끝부분의 합에 있어서 좀 더 세밀한 컨트롤이 필요하여, 

else 부분에서의 두번째 for문에서 분기를 넣었습니다.  (j == 0 or j == len(A[i-1]) or the others)

 

아이디어는 i번째 줄(리스트)의 연산을 할 때, i-1번째 리스트의 길이와 같게 해준다는 것입니다.

그리디 방법으로 풀었어요.

 

첫번째 연산에서는

그냥 자기 자신만 보면 됩니다. 끝

 

두번째 연산에서는 

첫번째 줄이 [a11], 두번째 리스트에서 [a21,a22]로 주어졌다고 할 때

두번째 리스트는 [a11 + a21, a11 + a22] 로 만들어줍니다.

 

세번째 연산에서는

두번째 리스트의 결과 [a11 + a21, a11 + a22]를 사용하여 세번째 리스트 [a31,a32,a33]과 연산을 실행합니다.

첫번째 원소의 경우 : a11 + a21 + a31 

두번째 원소의 경우 : a11 + a21 + a32, a11 + a22 + a32 중 큰 것 b

세번째 원소의 경우 : a11 + a22 + a33

-> [a11 + a21 + a31, b , a11 + a22 + a33] 이렇게 만들어줍니다.

 

네번째에도 동일한 방법으로,

[a11 + a21 + a31, b , a11 + a22 + a33] 과 [a41,a42,a43,a44]의 경우

첫번째 원소 : a11 + a21 + a31 + a41

두번째 원소 : a11 + a21 + a31 + a42, b + a42 중 큰 것

세번째 원소 : b + a43, a11 + a22 + a33 + a43 중 큰 것

네번째 원소 : a11 + a22 + a33 + a44 

 

이렇게 귀납적으로 구할 수 있겠고, 마지막 줄에서 가장 큰 원소를 return 해주면 됩니다.

프로그래머스에도 있는 문제더라고요. 레벨3이었나?