미소를뿌리는감자의 코딩
[백준 2024/03/21] 1932번 정수 삼각형 본문
728x90
https://www.acmicpc.net/problem/1932
1. 접근 방법
삼각형의 특정 위치에서의 삼각형 밑변까지 도달하기까지의 최댓값은 고정되어 있다고 생각하였다.
따라서 해당 위치에서의 최댓값을 memoization을 통해서 저장해둔다면, 값을 구할 수 있을 것이라 생각하였다.
따라서 만약 dictionary에 구하고자 하는 값이 있다면 그 값을 반환해 주었으며, 해당 dictionray에는 그 위치에서 얻을 수 있는 최댓값을 포함하고 있다.
만약, 밑변에 도달했다면, 더 이상 나아갈 길이 없기 때문에, 그 때는 자기 자신의 값을 반환해주었다.
dict_t[(a, b)] = triangle[a][b] + max(f(a + 1, b), f(a + 1, b + 1))
이런식으로, 현재 위치 값 + 왼쪽 오른쪽의 경우에서 최댓값을 더한 값을 dict[(a, b)] 의 최댓값이라 판단, 그 값을 memoization에 넣어주었다.
처음에는 잊고 triangle[a][b]를 더해주지 않아서, 값이 제대로 나오지 않았었다.
2. 코드
dict_t = {}
def f(a, b):
if (a, b) in dict_t:
return dict_t[(a, b)]
if a == height - 1:
return triangle[a][b]
dict_t[(a, b)] = triangle[a][b] + max(f(a + 1, b), f(a + 1, b + 1))
return dict_t[(a, b)]
height = int(input())
triangle = []
for i in range(height):
sub_triangle = [int(n) for n in input().split()]
triangle.append(sub_triangle)
print(f(0, 0))
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/03/23] 11651번 좌표 정렬하기 2 (1) | 2024.03.23 |
---|---|
[백준 2024/03/23] 11053번 가장 긴 증가하는 부분 수열 (0) | 2024.03.23 |
[백준 2024/03/20] 9461번 파도반 수열 (0) | 2024.03.20 |
[백준 2024/03/19] 9184번 신나는 함수 실행 (0) | 2024.03.19 |
[백준 2024/02/28] 1149번 RGB거리 (0) | 2024.02.28 |