#1932 정수 삼각형🔼

문제📝

결과😍

코드💻

n = int(input())
d = []

for i in range(n):
  d.append(list(map(int,input().split())))

for i in range(1,len(d)):
  for j in range(len(d[i])):
    if j == 0:
      d[i][0] += d[i-1][0]
    elif j == i:
      d[i][j] += d[i-1][j-1]
    else:
      d[i][j] += max(d[i-1][j-1],d[i-1][j])

print(max(d[-1]))

풀이💡

맨 밑의 자리, 즉, 4 5 2 6 5 각 자리에 올 수 있는 가장 큰 값을 구하고 그 값들 중에서 가장 큰 값을 출력해주면 된다.

1. 값을 입력받음
2. 맨 왼쪽 숫자들(d[i][0])과 맨 오른쪽 숫자들은 바로 위의 숫자들을 add
3. 나머지 가운데에 있는 숫자들은 왼쪽 위의 숫자와 오른쪽 위의 숫자 중 큰 숫자를 add
   • for문 한번 돌렸을 때 => 두번째 줄, 10 15
   • for문 두번 돌렸을 때 => 세번째 줄, 18 16 15

• dp 문제
  처음엔 그리디문제인가 했는데, 각각의 경우에서 가장 최대의 값을 찾는 것이 아니라 모든 가능한 경우의 수에서 최대의 값을 도출하는 것이었다. 따라서 dp로 문제를 풀어야 한다.

---

참고🙏

👉 [백준] 1932번: 정수 삼각형 - 파이썬