백준 1932번 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

많이 고전했다.

 

나는 알고리즘을 짤 때, 가능한 짧은 논리로 짜야한다고 생각한다.

 

조금이라도 코드가 길어지거나, 삽입하는 연산이 많아질수록 찝찝한 기분이 들기 때문이다.

 

하지만 이번 문제를 풀고 생각을 바꿔야겠다고 느꼈다.

 

코드

a = int(input())

array = []

def summ(i,n):

    if n == 0:

        array[i][n] = int(array[i-1][n])+int(array[i][n])

    elif n == len(array[i]) -1:

        array[i][n] = array[i][n] + array[i-1][n-1]

    else:

        array[i][n] = max(int(array[i-1][n-1]),int(array[i-1][n])) + int(array[i][n])

for i in range(a):

    array.append(list(map(int,input().split())))

for i in range(1,a):  

    for j in range(len(array[i])):

        summ(i,j)

       

print(max(array[-1]))

삼각형의 위에서 아래로 내려갈 때, 아래칸의 번호에 따른 규칙이 있다.

 

첫 번째는 위칸의 첫 번째, 2 <n <마지막칸 은 n, n-1중 큰 것, 마지막 칸은 n-1이 들어간다.

 

세 가지 케이스로 나눠서 dp연산으로 진행하였다.

 

나는 처음에 max() 함수를 사용하면, 요소들 중 배열의 인덱스 값이 벗어나는 게 있어도, 모두 벗어나지만 않는다면 정상적으로 수행될 거라 생각했다.

 

이번 문제로 확실히 그렇지 않다는것을 배웠다.

 

 

배운 점

1. 문제가 풀리게 끔 하는 모든 경우의 수를 항상 고려하자.