1932번: 정수 삼각형

1932번: 정수 삼각형

DP 문제다.

정수 삼각형의 맨 꼭대기에서 밑으로 내려오면서 선택된 수의 합이 최대가 되는 경로에 있는 수의 합을 구하는 문제.

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

 

시간 제한이 2초이므로 약 4,000만 번 연산이 가능한데, n의 범위는 500정도밖에 되지 않았다. 그래서 O(N^2)도 여유롭기 때문에 그냥 다 계산하면 되겠다라는 생각이 먼저 들었다.

 

먼저 dp 배열을 2차원 리스트로 만들어준다.

dp[i][j]에는 i번째 층에서 j번째 숫자를 선택했을 때 그 때까지의 최댓값이 저장되어 있다.

그리고 아래층으로 내려올 때, 만약 j번째 숫자를 선택하고 싶다면, 이전 층에서는 j번째 숫자 또는 j-1번째 숫자를 선택한 경우에만 가능하다.

 

i번째 층 j번째 숫자를 선택했을 때의 경로들 합의 최댓값  = i-1번째 층 j번째 숫자를 선택했을 때의 경로들 합의 최댓값, i-1번째 층 j-1번째 숫자를 선택했을 때의 경로들 합의 최댓값 중 큰 값 + i번째 층 j번째 숫자

이다.

 

즉, 

dp[i][j] = max(dp[i-1][j] + dp[i-1][j-1]) + arr[i][j]

라는 점화식을 얻을 수 있다.

 

# 1932번: 정수 삼각형
n = int(input()) # 정수 삼각형의 크기 n

dp = [[0 for _ in range(501)] for _ in range(501)] # 합이 최대가 되는 경로의 합을 저장하는 배열 dp -> 2차원 배열로 변환
arr = [[0 for _ in range(501)] for _ in range(501)] # 각 층의 수들을 저장하는 리스트 


# 각 층의 수들을 arr리스트에 대입
for i in range(1, n+1):
    temp = list(map(int, input().split()))
    for j in range(len(temp)):
        arr[i][j+1] = temp[j]

# 초기값 지정 -> 1층의 첫번째 값 -> arr[1][1]
dp[1][1] = arr[1][1]


# dp[i][j] = i번째 층의 j번째 숫자까지 오는 최댓값을 dp리스트에 저장
# 2층부터 dp리스트 갱신
for i in range(2, n+1):
    for j in range(1, i+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + arr[i][j]


# n번째 층 dp 값들 중의 최댓값을 출력하면 그게 정답
print(max(dp[n]))

여기서 조심해야할 점은 삼각형의 왼쪽 끝에서는 이전 층의 j-1번째 값을 구할 수 없고, 오른쪽 끝에서는 이전 층의 j번째 값을 구할 수가 없다.(인덱스 범위를 벗어남)

나는 그래서 삼각형의 수들을 저장하는 배열 arr에서 삼각형을 제외한 빈 값에 모두 0을 넣어줘서 해결했다.

어차피 최댓값을 구하는 것이기 때문에 0을 넣어도 상관없다고 생각했기 때문이다.

 

하지만 이럴 경우 arr 배열이 쓸 데 없이 많이 커지므로, 더 효율적으로 구할 수 있는 방법도 있다.

삼각형 왼쪽 끝, 오른쪽 끝, 끝이 아닌 경우 이렇게 3가지로 나눠서 dp테이블 값을 갱신해주는 것이다.

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

        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + arr[i][j]

 

그리고 더 최적화할 수 있는 방법도 있는데, arr배열을 만들지 않고, 그냥 dp 배열에 숫자값들을 저장하는 것이다.

어차피 최댓값을 갱신하는 거고, 밑의 층의 값이 (위에 층의 값의 합 + 밑의 층 해당 값)보다 절대로 클 수 없기 때문에 이런 식으로 해줘도 된다.

 

---

참고

 

[백준/파이썬] 1932 정수 삼각형