(파이썬) Baekjoon Online Judge 백준 1932 숫자삼각형
문제
풀이
n번째 층의 어떤 숫자가 선택되었을 때, 가능한 가장 큰 수를 찾는다.
가장 첫번째 수와 마지막 수는, 바로 위에 숫자에서 내려오는 길 밖에 없다.
내부에 있는 숫자들은, 인덱스를 i라 할때 한층 위의, i-1과 i 인덱스의 숫자까지의 합 중 큰 값을 선택한다.
lastsum[i]: 바로 윗층에서 i번째 숫자가 선택되었을 떄 가능한 가장 큰 합.
totalsum[i]: i번째 숫자가 선택되었을 때 가능한 가장 큰 합.
양끝의 경우 totalsum = lastsum + 현재값 되며
내부는 lastsum[i-1]과 lastsum[i]중에서 큰 값을 현재값과 더해준다.
코드
파이썬 (python)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
n=int(input()) num = [] num.append(list(map(int,input().split()))) lastsum = [] totalsum = [num[0][0]] for i in range(1,n): num.append(list(map(int,input().split()))) lastsum = totalsum totalsum =[] for j in range(0,i+1): if j == 0: totalsum.append(lastsum[0] + num[i][0]) # 가장 왼쪽 elif j < i and j > 0: totalsum.append(num[i][j]+ max(lastsum[j-1],lastsum[j])) # 내부 else: totalsum.append(lastsum[i-1] + num[i][j]) # 가장 오른쪽 print(max(totalsum)) |
숏코드 들어가보니 더 간단하게 푼거 같기도 한데..