[BOJ] 1932번 정수 삼각형 / 사용언어 : 파이썬(python)

※ 문제링크 

1932번: 정수 삼각형

※ 관련개념

메모이제이션 - 위키백과, 우리 모두의 백과사전

해당 문제는 메모이제이션과 피보나치수열의 개념을 응용해서 풀어야하는 문제였다. 각각의 정수 삼각형마다 피보나치를 적용하고 중간에 있는 값들은 최댓값을 구해서 반영하여 반복문을 돌려서 마지막 행까지 구한 다음, 최댓값을 출력하는 방식으로 문제를 해결했다. 구체적인 풀이방법과 코드는 아래와 같다.

1. 입력값을 2차원 리스트로 받아서 저장해준다.

2. 바텀업방식으로 각각의 자리에 올 수 있는 최댓값을 구해서 각 행의 값을 바꿔준다.

3. 반복문을 끝까지 돌린 후 마지막 행의 최댓값을 출력한다.

 

N = int(input())
arr = []
for i in range(N):
    arr.append(list(map(int, input().split())))
for i in range(1, N):
    for k in range(i+1): # 각 행의 첫번째 및 마지막 숫자는 가질 수 있는 값이 1개밖에 안됨.
        if k == 0:
            arr[i][k] = arr[i][k] + arr[i-1][k]
        elif k == i:
            arr[i][k] = arr[i][k] + arr[i-1][k-1]
        else:
            arr[i][k] = arr[i][k] + max(arr[i-1][k-1], arr[i-1][k]) 
                    
if N == 0:
    pass
else:
    print(max(arr[N-1]))

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.