❓ 문제
백준 실버1 문제 > 정수 삼각형
❗ 해결
DP 문제인데 조금 생각하다 보니 풀이법이 떠올랐다.
양 끝에 있는 숫자들은 어차피 더해지는게 정해진다.
즉, 리스트를
arr = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
이렇게 만들고,
반복문을 두번 돌린다.
for i in range(1,n):
for j in range(len(arr[i]):그러면 1번째 7, 2번째 3,8 3번째 8,1,0 ... 이 될것이다.
양 끝에 있는 숫자들은 바로 위에 숫자를 더해준다. 즉 j의 index가 0이거나 arr의 길이 - 1일때 바로위의 숫자를 더해주면 된다.
if j == 0:
d[i][j] = d[i-1][j] + arr[i][j]
elif j == len(arr[i])-1:
d[i][j] = d[i-1][j-1] + arr[i][j]그렇지 않은 경우 문제에서 오른쪽이나 왼쪽 대각선의 수만 더할 수 있다고 했으므로
오른쪽이나 왼쪽 대각선의 수 중 더 큰수를 넣으면 된다.
else:
d[i][j] = max(d[i-1][j-1], d[i-1][j]) + arr[i][j]중간에 반례를 못찾아서 조금 헤맷는데,
처음 반복문을 1부터 시작해야지, 0으로 시작했다가
입력이
1
1
이면 2가 되는 상황이 발생해서.. 수정했다.
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
d = [[0 for _ in range(n)] for _ in range(n)]
d[0][0] = arr[0][0]
for i in range(1, n):
for j in range(len(arr[i])):
if j == 0:
d[i][j] = d[i-1][j] + arr[i][j]
elif j == len(arr[i])-1:
d[i][j] = d[i-1][j-1] + arr[i][j]
else:
d[i][j] = max(d[i-1][j-1], d[i-1][j]) + arr[i][j]
print(max(d[n-1]))
