# Chap 16. DP - Q32. 정수 삼각형

- Author: @mildsalmon
- Published: 2021-10-24
- Updated: 2021-10-24
- Source: http://blex.me/@mildsalmon/chap-16-dp-q32-%EC%A0%95%EC%88%98-%EC%82%BC%EA%B0%81%ED%98%95
- Tags: 파이썬, 알고리즘, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, 백준, dp

---

# 1. 정수 삼각형

- 난이도
	- 중하
- 풀이 시간
	- 30분
- 시간 제한
	- 2초
- 메모리 제한
	- 128 MB
- 출처
	- [1932번: 정수 삼각형 (acmicpc.net)](https://www.acmicpc.net/problem/1932)

### A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

### B. 💡 내 답안

##### a. 😊 1차 시도 (성공)

```python

n = int(input())

array = [[] for i in range(n)]

for i in range(n):
    temp = list(map(int, input().split()))

    array[i] = temp

dp = [i[:] for i in array]

dp[0] = array[0]

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

print(max(dp[-1]))

```

##### b. 🙄 회고

> 내 풀이

- 31번 문제처럼 DP를 사용하였다.

> 반성

- 이 글을 쓰면서 코드를 다시 보는데, 해석하기 난해하다. 그리고 좀 잘못푼 것 같다.
	- if-elif-else로 구성하면, 윗층에 값을 한 개밖에 비교를 못할텐데 뭔가 이상하게 코드를 짯다.

### C. 🧐 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

문제를 풀면 아래처럼 풀리게 된다.

![](https://static.blex.me/images/content/2021/10/24//2021_10_24_21_WqTA6FugmZjw0z83kNst.jpg)

다만, 저런식으로 입력 리스트를 피라미드 형태로 구성하면서 풀기보다, 리스트에 어떤 모양으로 들어갈지 생각해서 푸는게 더 편하다.

2차원 리스트를 생각하면 이렇게 값이 들어간다.

![](https://static.blex.me/images/content/2021/10/24//2021_10_24_21_IYC6Wb6yfDPKq5BoEA1F.jpg)

그럼 값은 아래처럼 계산할 수 있다.

![](https://static.blex.me/images/content/2021/10/24//2021_10_24_21_4eOarskaWFbxSIbigi9A.jpg)

그런데, 31번에서 푼 방식처럼, 아랫층 값을 구성할 수 있는 윗층 값들을 비교한 후 더 큰 값과 아랫층 값을 더해서 최상의 결과를 구하는 것이 연산 횟수도 적고, 빠르지 않을까?

![](https://static.blex.me/images/content/2021/10/24//2021_10_24_21_vecWDxS43Rl3DQzm6Xkl.jpg)

그럼 $dp_{(n, m)} = max(dp_{(n-1, m-1)}, dp_{(n-1, m)}) + array_{(n, m)}$ 이런 공식이 나온다.

##### a. 책 답안

[python-for-coding-test/2.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/16/2.py)

# 참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

[1932번: 정수 삼각형 (acmicpc.net)](https://www.acmicpc.net/problem/1932). Baekjoon. (accessed Oct 24, 2021)