오늘의 문제
https://www.acmicpc.net/problem/1932
예제 입력값에서 최적의 경로는 7-3-8-7-5 총합 30이다.
이를 통해 알 수 있는 점은 “무조건 큰 값만을 찾는다고 해서 누적합이 최대가 되지 않는다” 이다.
tri라는 이중 리스트로 이루어진 삼각형배열을 만든 후
윗단부터 차례차례 더해진 값들을 tri에 저장하여 마지막에 출력만 하면 된다.
앞서 풀어봤던 rgb거리 문제와 유사했다.
포인트 쳌쳌
- 그림의 삼각형을 코드로 표현할 때 i층, j번째 인덱스를 갖는 이중 리스트를 사용했다.
- 삼각형의 상단 꼭짓점(예제에서는 7이 위치한 곳)을
i = 0이라고 가정한다. - j=0 또는 j=i 일 경우는 윗줄(i-1)의 같은 인덱스(j)의 값을 가져와 더해준다.
- 예제의 경우(꼭짓점을 제외하고 생각해보자. )
- j=0일 때: 3, 8, 2, 4 가 이에 해당한다.
- j=i일 때: 8, 0, 4, 5 가 이에 해당한다.
- 그 외의 경우는 윗줄(
[i-1])의[j-1]값과[j]값을 비교하고, 더 큰 값을 선택하여 더해준다.- 예제의 경우
- i=2 줄은 [8, 1, 0] 을 갖는다. 이때 1은 윗줄 [3, 8]에서 더 큰 값인 8과 더해진 후 저장되어야 한다.
풀이 코드
n = int(input())
tri = [[0]*i for i in range(1, n+1)] #삼각형 구조 만들기
#삼각형 안에 입력값 채우기
for i in range(n):
now = list(map(int, input().split()))
for j in range(len(now)):
tri[i][j] = now[j]
#모든 위치를 조회하며, 각 위치마다의 누적 합계를 순차적으로 저장한다.
for i in range(1, len(tri)):
for j in range(i+1):
now = tri[i][j]
if j == 0:
tri[i][j] = tri[i-1][j]+now
elif j == i:
tri[i][j] = tri[i-1][-1]+now
else:
tri[i][j] = max(tri[i-1][j-1]+now, tri[i-1][j]+now)
#삼각형의 가장 하단부에서 최대값을 찾아 출력
print(max(tri[-1]))
채점 결과
