[백준 1932] 정수 삼각형

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

이 문제는 그림을 참고해야한다.

위에서 아래로 규칙을 통해 수를 선택해 더했을 때 맨 밑에서 최댓값을 찾는 것이다.

---

접근

백준의 RGB거리와 유사한 방법이다.

위에서 아래로 내려올 때 최댓값을 더해주면서 내려오도록 한다.

이러한 문제도 삼각형의 높이를 줄이면서 어떤 규칙이 있는지 찾아야한다.

 

구현

정수 삼각형의 정보를 2차원 리스트인 samgak에 저장을 한다.

y는 층수, x는 해당 층의 정수의 자리를 나타내는데

0번째의 수는 이전의 0과 더하고 끝자리는 이전의 끝자리 이전을 더한다

그 외에는 이전 층의 x-1과 x 중 최댓값을 더해나간다.

if N == 1:
    answer = samgak[0][0]
else:
    for y in range(1, N):
        for x in range(len(samgak[y])):
            if x == 0:
                samgak[y][x] += samgak[y-1][0]
            elif x == len(samgak[y])-1:
                samgak[y][x] += samgak[y-1][len(samgak[y])-2]
            else:
                samgak[y][x] += max(samgak[y-1][x-1], samgak[y-1][x])
    answer = max(samgak[N-1])

---

전체 코드

import sys
input = sys.stdin.readline
N = int(input())

samgak = [list(map(int, input().split())) for _ in range(N)]

if N == 1:
    answer = samgak[0][0]
else:
    for y in range(1, N):
        for x in range(len(samgak[y])):
            if x == 0:
                samgak[y][x] += samgak[y-1][0]
            elif x == len(samgak[y])-1:
                samgak[y][x] += samgak[y-1][len(samgak[y])-2]
            else:
                samgak[y][x] += max(samgak[y-1][x-1], samgak[y-1][x])
    answer = max(samgak[N-1])

print(answer)