[코테 스터디] DP, 정수 삼각형

Q32. 정수 삼각형

🐣문제

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


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


백준 링크 | https://www.acmicpc.net/problem/1932

🐥풀이

DP 테이블을 생성 및 초기화 하고, 왼쪽 또는 오른쪽 대각선 위의 수 중 큰 수를 선택해 더해 내려간다.


입력은 아래와 같이 주어지므로,
0
0 0
0 0 0
0 0 0 0
...
[i][j] 기준으로 왼쪽 대각선 위는 [i-1][j-1], 오른쪽 대각선 위는 [i-1][j] 와 같은 인덱스를 가진다.


또한, 삼각형에서 한 층씩 내려올 때마다 한 줄의 길이가 1씩 늘어나는 것을 감안 해야한다.
즉 j-1>=0과 j<i의 조건에 따라 DP 테이블을 업데이트 해야한다.
(j-1<0) 왼쪽 대각선 위의 수 존재 X
(j>=i) 오른쪽 대각선 위의 수 존재 X


DP 식은 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])+triangle[i][j]로 볼 수 있겠다. (triangle은 입력 삼각형 값)

🐓코드

# 입력값
n = int(input())
triangle = [list(map(int, input().split())) for _ in range(n)]

# DP 테이블
dp = [[0]*(i+1) for i in range(n)] # DP 테이블 준비
dp[0][0] = triangle[0][0] # DP 테이블 초기화

# DP 시작
for i in range(1,n):
  for j in range(i+1):
    # 오른쪽 대각선 위
    if j-1<0 and j<i:      
      dp[i][j] = dp[i-1][j]+triangle[i][j]
    # 왼쪽 대각선 위
    elif j-1>=0 and j>=i:  
      dp[i][j] = dp[i-1][j-1]+triangle[i][j]
    # 왼쪽 대각선 위, 오른쪽 대각선 위
    elif j-1>=0 and j<i:  
      dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])+triangle[i][j]

result = 0


for i in range(n):
  result = max(result, dp[-1][i])

# 결과 출력
print(result)

⭐2022.05.09

왼쪽과 오른쪽 대각선 위의 인덱스와 그 범위 조건을 잡는 것이 조금 어려웠다. ...공부하자^.^