[Python] 백준 1932번:정수 삼각형 / 문제 풀이, 설명

[Python] 백준 1932번:정수 삼각형 / 문제 풀이, 설명

---

º 코드

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

k=2
for i in range(1,times):
    for j in range(k):
        if j == 0:
            ar[i][j] = ar[i][j] + ar[i-1][j]
        elif i == j:
            ar[i][j] = ar[i][j] + ar[i-1][j-1]
        else:
            ar[i][j] = max(ar[i-1][j-1],ar[i-1][j])+ar[i][j]
    k+=1
print(max(ar[times-1]))

º 풀이

1. 풀이 과정

1. 양 끝의 수는 바로 위에 수밖에 받을 수 없다. 그리고 양 끝이 아닌 수들은 둘 중 하나를 받을 수 있다.
   1. i=2부터 시작해서 양 끝의 수, 그렇지 않은 수로 조건을 나눈다.
   2. 양 끝이 아닌 수들은 [i-1][j], [i-1][j-1] 중 더 큰 값을 선택하고 [i][j]번째 수를 더해서 [i][j]에 대입한다.
2. 그리고 times - 1 번째 수 중에서 가장 큰 값을 출력한다.

---

º 도움이 된 사이트

• https://pacific-ocean.tistory.com/148

[백준] 1932번(python 파이썬)