[백준] 1932 정수 삼각형 (파이썬 Python)

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

1932번: 정수 삼각형

문제 설명

---

풀이 과정

• 나의 풀이

① 이 문제에서 직관적으로 파악한 것은 '위에서 아래로 순차적으로 진행되는 과정 속에서 최대인 경우를 찾는 것이니깐... DP문제인가...?'였다.

② DP문제인듯한 느낌을 받은 상태에서 예제문제의 과정을 직접 수행해보며 확인해보았다. 

 위에서 아래로 내려오며 빨간 O표 부분은 과정 속에서 최선의 방법이고, 빨간 X표 부분은 과정 속에서 버려지는 부분이다.

③ 아이디어 열기

(1) 입력값

 처음 입력되는 값인 5값은 5줄의 삼각형 크기의 숫자가 주어지고, 4번의 과정을 거친다는 것을 의미하는듯했다.

 7

 3 8

 8 1 0 

 2 7 4 4

 4 5 2 6 5

 로 입력되는 값은 행과 열로 구분되는 이차원리스트에 저장하였다.

(2) dp식 세우기

 일단.. 위의 문제와 같은 경우 n값이 입력되었을 때 n-1번의 계산과정이 이루어지므로 for구문을 통해 행을 나타내어준다.

 행을 나타내는 for구문 안에 이중 for문을 구성하여 열끼리의 계산과정 속 버리는 값은 버리고 챙기는 값은 챙기는 과정을 거쳤다.

 예를 들어, i = 2인 경우 3번째 줄에서 8에 오는 화살표와 0에 오는 화살표는 1개이기에 어쩔 수 없이 최선의 경우가 된다. 하지만 1에 오는 화살표는 2개이기에 둘 중 하나의 경우는 버려야만 한다. 이를 점화식으로 나타내면 다음과 같다.

 1. i행 0번째 항목 : i-1행 0번째 항목을 그대로 더해줌.  

 2. i행 i번째 항목 : i-1행 i번째 항목을 그대로 더해줌.

 3. 다른 경우들 : i-1행 j-1번째 항목과 i-1행 j번째 항목 중 더 큰 경우를 더해줌.

 이를 코드화하면 다음과 같다.

# 1932  정수 삼각형 (파이썬 Python)
n = int(input())
dp = []

for i in range(n) :                            ## 입력값 이차원리스트 형태로 dp테이블에 저장하기
    dp.append(list(map(int,input().split())))

print(dp)
print(dp[1][0])

for i in range(1,n) :                           ## 행을 기준으로 for문 구성
    for j in range(0,i+1) :                     ## 열을 기준으로 for문 구성
        if j == 0 :
            dp[i][0] += dp[i-1][0]              # 0열끼리 더하기
        elif j == i :
            dp[i][j] += dp[i-1][j-1]            # 마지막 열끼리 더하기
        else :
            dp[i][j] += max(dp[i-1][j-1],dp[i-1][j])    # 두 화살표중 더 큰 경우 받아들이기

print(max(dp[n-1]))                 # n-1행에서의 최댓값 출력

---

후기

  dp문제임을 빠르게 캐치해서 비교적 쉽게 풀린듯하다.