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

문제 설명

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

1932번: 정수 삼각형

 

주어진 그림처럼 삼각형 모양으로 숫자가 주어진다.

맨 위부터 시작해 제일 아래쪽으로 탐색을 하게되는데,

현재 지점에서 다음 지점(아래 지점)으로 이동할 때는, 왼쪽대각선과 오른쪽 대각선으로만 갈 수 있다.

 

이 방법으로 탐색했을 때, 탐색경로에 있는 숫자들을 모두 더했을 때의 최대가 되는 경로를 구하는 문제이다.

---

풀이 과정

이 문제는 DP(다이나믹 프로그래밍)을 이용해 앞에서부터 최댓값을 저장해나가며 푸는 문제이다.

가장 첫번째 열에 있는 숫자(7, 3, 8, 2, 4)들은 선택의 여지 없이 이전의 가장 왼쪽 수를 선택해야 한다.

예를 들어, 3번째 줄의 가장 왼쪽 숫자인 8은 2번째 줄의 3을 선택했을 때의 경로를 따라야 하며

4번째 줄의 가장 왼쪽 숫자인 2는 3번째 줄의 8을 선택했을 때의 경로를 따라야 한다.

 

그 이외의 숫자들은 이전(위) 숫자 두개 중 최댓값을 선택할 수 있다.

 

이러한 특징을 반영하여 DP배열을 2차원으로 만들어 아래와 같은 코드를 짤 수 있다.

DP[1][0]에는 1번째 줄의 0번째 수를 선택했을 때의 최댓값을 저장하고

DP[1][1]에는 1번째 줄의 1번째 수를 선택했을 때의 최댓값을 저장한다.

 

이를 파이썬 코드로 나타내면 다음과 같다.

n = int(input())

arr = []
dp = [[0]*n for _ in range(n)]
for i in range(n):
    arr.append(list(map(int, input().split())))

dp[0][0] = arr[0][0]

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

print(max(dp[n-1]))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !