[백준/Python] 1932 정수 삼각형

[백준/Python] 1932 정수 삼각형

정답 코드 및 설명

전체 코드

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

# 삼각형 데이터 입력받기
for _ in range(n):
    triangle.append(list(map(int, input().split())))

# 동적 프로그래밍을 위한 2차원 DP 테이블 초기화
dp = [[0] * n for _ in range(n)]
dp[0][0] = triangle[0][0]

# 삼각형의 각 층을 순회하며, 각 위치에서의 최대 합 계산
for i in range(1, n):
    for j in range(i + 1):
        # 왼쪽 대각선 위에서 내려오는 경우
        if j > 0:
            left_up = dp[i-1][j-1]
        else:
            left_up = 0
        
        # 바로 위에서 내려오는 경우 (오른쪽 대각선을 고려하지 않음, 삼각형의 형태상 바로 위에서 내려올 수 없음)
        if j < i:
            up = dp[i-1][j]
        else:
            up = 0
        
        # 현재 위치에서의 최대 합 업데이트
        dp[i][j] = max(left_up, up) + triangle[i][j]

# 마지막 층에서의 최대값 찾기
result = max(dp[n-1])

print(result)

코드 설명

1. 삼각형 데이터 입력 받기

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

크기가 n 으로 입력 받은 값을 이용하여 삼각형을 입력 받는다.

2. 동적 프로그래밍을 위해 dp 테이블을 만들어준다

# 동적 프로그래밍을 위한 2차원 DP 테이블 초기화
dp = [[0] * n for _ in range(n)]
dp[0][0] = triangle[0][0]

dp 테이블을 0으로 초기화 하고 처음 0,0 은 삼각형의 맨 위 꼭짓점 부분으로 비교할 필요가 없으니 설정해준다.

3. 삼각형의 각 층을 순회하면서, 각 위치에서의 최대 합을 계산한다.

for i in range(1, n):
    for j in range(i + 1):

i 는 1부터 n-1 까지이다 이는 삼각형 2번째 줄부터 순회한다는 뜻이고
j 는 0부터 i+1 까지인데 이는 i번째 줄의 항목을 순회한다는 뜻이다.

        # 왼쪽 대각선 위에서 내려오는 경우
        if j > 0:
            left_up = dp[i-1][j-1]
        else:
            left_up = 0
        
        # 바로 위에서 내려오는 경우 (오른쪽 대각선을 고려하지 않음, 삼각형의 형태상 바로 위에서 내려올 수 없음)
        if j < i:
            up = dp[i-1][j]
        else:
            up = 0
        
        # 현재 위치에서의 최대 합 업데이트
        dp[i][j] = max(left_up, up) + triangle[i][j]

아래로 내려갈 경우 2가지 경우가 있다.

• 왼쪽 대각선 위에서 내려올 경우
  이 경우는 현재 숫자의 위치가 그 층의 첫번째면 내려올수 없기에, j > 0 이라는 조건을 먼저 필터링해준다. dp[i-1][j-1] 에서 현재 숫자를 더한 값을 고려한다
• 바로 위에서 내려올 경우
  이 경우는 현재 숫자의 위치가 그 층의 마지막 숫자가 아닐때만 가능하다. 즉, j < i 일 때이다. 이 경우는 dp[i-1][j] 에서 현재 숫자를 더한 값을 고려한다.

그 후 현재 위치에서 구한 최대 합을 업데이트 한다. dp[i][j] 에 현재 위치 값 triangle[i][j] 와 이전에 구한 왼쪽 위, 바로 위 를 비교해서 높은 것을 더해준다.

4. 마지막 층에서 최대값 찾기

# 마지막 층에서의 최대값 찾기
result = max(dp[n-1])

print(result)

결과적으로 마지막 까지 간 값 중에서 최대값을 찾으면 되기 때문에, max(dp[n-1]) 해서 정답을 찾을 수 있다.