시간 2초, 메모리 128MB
input :
- 삼각형의 크기 n(1 <= n <= 500)
- n + 1번째 줄 까지 정수 삼각형
output :
- 합이 최대가 되는 경로에 있는 수의 합.
삼각형이 트리모양을 이루고 있다. 이진 완전 트리는 아니기에 노드 넘버 / 2 등은 이용할수 없다.
삼각형마다의 길이가 다르다. 이를 나타내는 변수가 필요하다.
아이디어 :
left, right 의 값이 더 큰 것을 찾는 것인데.
그 결과는 부모의 노드가 어떤 값을 가지냐로 볼수 있다.
반복문이 돌며 max(부모의 현재 값, 원 부모의 값 + 자식의 값)
-> 원 노드들의 값, 계산을 한 값들을 저장할 리스트 필요.
(이렇게 적어 놓고도 answer리스트 안 만드는 바람에 20분 허비함....)
부모에서 자식을 찾든, 자식에서 부모를 찾든 데이터를 찾아야 한다.
1. 자식에서 부모를 찾으려 했을 때 :
삼각형의 크기로 입력을 받은 숫자로 가장 마지막 인덱스 - n을 한 경우에 이는 부모 인덱스가 된다. 부모 인덱스를 찾아낼수 있는 아이디어.
n을 뺄 때는 right_child에서의 부모를
n - 1을 뺄 때는 left_child에서의 부모를 찾을 수 있다.
그러나, 각 줄에서 n을 빼면서 가다가 그 윗줄로 이동하는 조건을 또 찾아야 하는데 너무 복잡하다.
위 1번으로 생각을 하다가 30분을 허비한 듯.
2. 부모에서 자식을 찾으려 할 때 :
parent와 child간의 gap은 n까지 발생 할 수 있는데.
gap의 시작은 1이다. left_child와는 gap만큼, right_child와는 gap + 1만큼의 차이가 있다.
parent 가 0 일 때, child 는 1, 2 --> gap 1 // 반복 1번 수행
다음 줄로 이동. gap + 1
parent 가 1 일 때, child 는 3, 4 --> gap 2 // 반복 2번 수행
다음 줄로 이동. gap + 1
`
다음 줄로 이동. gap = n - 1
parent가 6 일 때, child 는 10, 11 --> gap n - 1. // 반복 n번 수행
gap에 대한 for으로 문제를 풀자.
정답을 구하는 리스트와, 삼각형 리스트는 따로 존재하는데 우리가 이 반복문을 수행하는 목적은 정답리스트를 채우기 위해서 이다.
정답[자식] = max(정답[자식], 삼각형[자식] + 정답[부모])
정답 코드 :
n = int(input())
triangle = []
answer = []
for i in range(n):
data = list(map(int, input().split()))
for j in range(len(data)):
triangle.append(data[j])
answer.append(data[j])
find_child_idx = 0
for gap in range(1, n):
for _ in range(gap):
left_child_idx = find_child_idx + gap
right_child_idx = find_child_idx + gap + 1
answer[left_child_idx] = max(answer[left_child_idx], triangle[left_child_idx] + answer[find_child_idx])
answer[right_child_idx] = max(answer[right_child_idx], triangle[right_child_idx] + answer[find_child_idx])
find_child_idx += 1
print(max(answer))
