[백준] 1932번 정수 삼각형 - Python

백준 실버1 1932번 정수 삼각형 - Python

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

---

문제

import sys
input = sys.stdin.readline
N = int(input().rstrip())
t = [[] for i in range(N)]
for i in range(N):
    t[i] += list(map(int, input().rstrip().split()))
cnt = t[0][0]
nIdx = 0
for i in range(1, N):
    n = max(t[i][nIdx], t[i][nIdx+1])
    nIdx = t[i].index(n)
    cnt += n
print(cnt)

다음은 문제의 의도와는 다르게 푼 코드입니다.

 

출력 예시에서부터 틀려서 다시 한번 생각해보니

위에서 내려가면서 큰수만 골라 더하는 것이 아니라 모든 경우의 수를 따져 가장 큰 합을 구해야 합니다.

 

그래서 밑에서부터 올라가기로 했습니다.

 

예시를 통해서 설명해드리겠습니다.

• 아래에서 부터 올라간다고 생각해봅시다. 
• 먼저 4와 5를 비교합니다. 5가 더 크지요? 더 큰 5를 2에 더해줍니다.
• 4와 5만 놓고 비교하는 이유는 2에서 내려갈 때 4와 5 둘 중 하나로 갈 수 밖에 없기 때문입니다.
• 이 과정을 5번째 줄 전체에서 반복합니다.

이렇게 되겠지요?

 

그럼 이 과정을 모든 줄에서 반복합니다.

마지막에는 30으로 연산 결과가 나올 것입니다.

그래서 이 계산을 코드로 옮겨보면

---

코드

맞았습니다가 뜬 코드입니다. - 메모리 35608KB | 시간 120ms | 코드 길이 274B

import sys
input = sys.stdin.readline
N = int(input().rstrip())
t = [[] for i in range(N)]
for i in range(N):
    t[i] += list(map(int, input().rstrip().split()))
for i in range(N-1, 0, -1):
    for j in range(i):
        t[i-1][j] += max(t[i][j], t[i][j+1])
print(t[0][0])

이렇게 되겠습니다.

---

후기

김방구뽕뽕이가 패트와 매트 브금 한시간짜리를 줘서 들으면서 코드짜려고 했는데

점점 머리에 꽃이 피는 기분이 들어서 껐습니다....

 

머리에 해바라기 날 뻔 봤네요 ;; 김방구뽕뽕이를 조심하세요;;;;