728x90
반응형
※ 문제링크
※ 관련개념
해당 문제는 메모이제이션과 피보나치수열의 개념을 응용해서 풀어야하는 문제였다. 각각의 정수 삼각형마다 피보나치를 적용하고 중간에 있는 값들은 최댓값을 구해서 반영하여 반복문을 돌려서 마지막 행까지 구한 다음, 최댓값을 출력하는 방식으로 문제를 해결했다. 구체적인 풀이방법과 코드는 아래와 같다.
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 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
728x90
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 1463번 1로 만들기 / 사용언어 : 파이썬(python) (0) | 2021.12.23 |
---|---|
[BOJ] 1149번 RGB거리 / 사용언어 : 파이썬(python) (0) | 2021.12.23 |
[BOJ] 9461번 파도반 수열 / 사용언어 : 파이썬(python) (0) | 2021.12.22 |
[BOJ] 1904번 타일 / 사용언어 : 파이썬(python) (0) | 2021.12.22 |
[BOJ] 9184번 신나는 함수 실행 / 사용언어 : 파이썬(python) (0) | 2021.12.22 |
댓글