[Python][백준] 1932. 정수 삼각형/ DP (S2)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

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

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

 

1. 전형적인 DP 문제이다. 

 

2. 반복문은 크게 2가지가 필요하다. 

- 정수 삼각형 두 번째 줄에서 N 번째 줄까지의 반복문

- 정수 삼각형 각 줄에 있는 리스트의 크기만큼 반복문
(이것은 새로운 값 갱신을 위한 것)

 

3. 반복문 이후 조건문이 필요하다. 

조건절은 크게 3가지로 구분 할 수 있다.

- 정수 삼각형 줄에 첫 번째 인덱스인 경우
- 정수 삼각형 줄에 마지막 인덱스인 경우
- 정수 삼각형 줄에 그 외의 경우

 

4. 이후 적절하게 인덱싱하여 정수 삼각형의 값들을 갱신하면 된다.  

 

🔎내 풀이 방식

N = int(input())

graph = []
dp = []
for _ in range(N):
    tmp = list(map(int,input().split()))
    graph.append(tmp)
for i in range(1,N+1):
    dp.append([0]*i)
dp[0][0] = graph[0][0]

for k in range(N-1):
    # 양끝 0,N DP 값 선언 
    dp[k+1][0] = dp[k][0]+graph[k+1][0]
    dp[k+1][len(dp[k])] = dp[k][len(dp[k])-1]+graph[k+1][len(dp[k])]
    for i in range(1,len(dp[k])):
        dp[k+1][i] = max(dp[k][i-1]+graph[k+1][i],dp[k][i]+graph[k+1][i])    
print(max(dp[-1]))

 

1. 내 풀이에서는 graph 리스트와 dp 리스트 두개를 만들었다. 

(일반적인 dp 풀이에서 이런방식으로 진행 되는 듯 하다.)

 

2. 새로운 dp 리스트를 만들었기 때문에, 초기 값 설정이 필요하다. 

 

3. 이후 정수 삼각형 해당 줄에 0번째와 마지막 인덱스를 설정 해주었다.

 

4. 그리고 그 외의 dp 값들을 잘 인덱싱하여 채워주면 된다. 

 

→ 굳이 dp 리스트 없이 graph를 갱신하는 방향으로 진행해도 되는 문제였다.

또 아쉬웠던 부분은  반복문 인자를 k라 두어 인덱싱의 가독성이 많이 떨어졌다.

 

 

📌  문제 코멘트

아주 전형적인 DP 문제라 잘 익혀두어야 한다. 

인덱싱 부분이 좀 헷갈리는데,

이런 경우 손으로 하나 하나 풀어서 봐야한다. 

왠만한 복잡한 문제들도 뭉텅이를 하나 하나 해결하면 결국 풀어질 것 이다 !

---

📚문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제 입력 1 복사

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력 1 복사

30