[백준] 1932 : 정수 삼각형 (Python)

 

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

 

 

---

 

아이디어

이번 문제는 결론적으로는 dp로 접근해야 한다. 실버 등급의 문제이지만, dp에 대한 개념을 정확히 알아야 접근 가능하다. dp 접근까지 필자의 사고 과정을 통해 문제 해결 과정을 살펴보는 것을 추천한다. 이제 차근차근 알아보자.

 

1번째 접근 : 그리디(Greedy)

경로 길이의 최댓값을 요구하는 문제이므로, 가장 먼저 그리디를 떠올렸다. 정수 삼각형을 트리로 생각하여, 다음의 가설을 세웠다.

'각 레벨에서 최댓값을 선택해나가는 방법'

즉, 지역적 답들을 선택해나가 전역답과 근사한지를 체킹하는 것이 필요하다. 그러나, 다음 사진과 같은 문제점을 발견하였다.

그리디 접근 시 문제점

레벨 2에서의 지역 최댓값은 8이고, 레벨 3에서의 최댓값도 8이다.

그러나, 이들을 모두 선택하기 위해서는 8에서 8로 가는 경로(간선)이 존재해야하지만, 존재하지 않는다. 그럼으로 전역답과 틀려지기 때문에, 다른 알고리즘을 생각해보았다.

 

2번째 접근 : 완전 탐색

문자 그대로, 각 레벨까지의 누적합을 계속 비교해나가는 방식이다. 이 또한, 예제를 통해 구체적인 탐색 과정을 테스트했을 때, 2가지 문제점을 발견하였다.

완전 탐색 과정

1번째 문제점은 시간 초과의 가능성이다. 시간복잡도는 O(n*n)에 가깝고 n의 입력은 500까지 가능하기 때문에, 시간 초과의 가능성이 존재한다.

2번째 문제점은 중복 연산이다. 이는 시간 초과 가능성을 더해주는 요소이며, 해당 알고리즘의 핵심 문제점이다. 위의 사진에서 빨간색 박스에 해당되는 부분으로, 다음과 같이 시각화할 수 있다.

중복 연산에 대한 고찰

1값에 해당되는 부모는 3과 8로써, 계산 과정에서 봤을 때 사실 같은 경로가 아니라는 것을 알 수 있다.

• 7 -> 3 -> 1 경로는 7 -> 8 -> 1 경로와 다르다.

이러한 사실을 바탕으로, 레벨이 더 깊어진다면 사진과 같이 불필요한 중복 과정이 들어갈 수 있음을 확인할 수 있게 된다. 그러므로, 다른 알고리즘을 탐색해야 한다.

 

---

 

트리 관점에서 보았을 시, 경로를 찾아나가는 과정과 중복 연산이 존재한다는 사실을 알 수 있다. 이를 통해, 메모제이션 기법을 떠올릴 수 있고, 이는 dp와 연결되기 때문에 dp로 접근해야겠다는 생각을 해볼 수 있다.

 

3번째 접근 : DP

다음과 같이, 3가지의 조건에 부합되기 때문에 DP로 접근이 가능하다.

DP의 3가지 조건

 

그렇다면, dp 테이블을 어떻게 설정해야 할까?

 

DP 테이블 설정 1번째 : 특정 레벨까지의 누적 최댓값을 저장해나가는 방법

DP[x]로 설정한다는 의미이다. 이는 '트리의 x레벨까지의 누적 최댓값'을 의미한다.

• ex) DP[0] = 7 : 트리 0레벨의 누적 최댓값은 7이다.
• ex) DP[1] = 15 : 트리 1레벨까지의 누적 최댓값은 15이다.

이를 토대로, 예제 입력 1번 케이스의 탐색 과정을 살펴보자.

예제 입력 탐색 과정

이전의 정보인 dp[1]과 누구를 비교해야할지 판별을 할 수 없기 때문에, dp[2]부터 문제가 발생한다.

dp[2]의 값을 결정하기 위해서는 3가지의 비교가 필요하다.

• 맨 왼쪽을 타고 가는 경로 : 7 -> 3 -> 8
• 중간에 해당되는 트리 레벨2의 1 : MAX(7 -> 3 -> 1, 7-> 8 -> 1)
• 맨 오른쪽을 타고 가는 경로 : 7 -> 8 -> 0

즉, 경로에 맞춘 경우의 수대로 비교가 필요하다는 것이다. 그러므로, DP 테이블의 설정을 다음과 같이 변경해야함을 알 수 있다.

 

DP 테이블 설정 2번째 : 특정 노드까지의 누적 최댓값을 저장해나가는 방법

DP 테이블을 2차원 배열로써 다음과 같이 정의한다.

DP[x][y] 예시

• dp[x][y] : 트리의 x레벨 중, 노드 y번을 가는데 걸리는 경로 길이의 최댓값 
• 초기 dp 테이블(배열) 세팅 : 정수 삼각형 값들을 저장시켜놓은 2차원 배열.
  • dp = [ [7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

 

이를 바탕으로, 예제 입력 1번 케이스에 대한 구체적인 탐색 과정을 살펴보자.

초기 dp 테이블 내용	j = 0	j = 1	j = 2	j = 3	j = 4
dp[0]	7
dp[1]	3	8
dp[2]	8	1	0
dp[3]	2	7	4	4
dp[4]	4	5	2	6	5

 

탐색 내용	j = 0	j = 1	j = 2	j = 3	j = 4
dp[0]	dp[0][0] = 7
dp[1]	dp[0][0] + dp[1][0] = 7 + 3 = 10	dp[0][0] +  dp[1][1] = 7 + 8 = 15
dp[2]	맨 왼쪽를 타는 경로 dp[1][0] + dp[2][0] = 10 + 8 = 18	중간 MAX( dp[1][0] + dp[2][1] , dp[1][1] + dp[2][1] ) = MAX(11,16)=16	맨 오른쪽을 타는 경로 dp[1][1] + dp[2][2] = 15 + 0 = 15
dp[3]	맨 왼쪽 dp[2][0] + dp[3][0] = 18 + 2 = 20	중간 MAX( dp[2][0] + dp[3][1] , dp[2][1] + dp[3][1] ) = MAX(25,23)=25	중간 MAX( dp[2][1] + dp[3][2] , dp[2][2] + dp[3][2] ) = MAX(20,19)=20	맨 오른쪽 dp[2][2] + dp[3][3] = 15 + 4 = 19
dp[4]	맨 왼쪽 dp[3][0] +  dp[4][0] = 24	중간 MAX( dp[3][0] + dp[4][1] , dp[3][1] + dp[4][1] ) = MAX(25,30)=30	중간 MAX( dp[3][1] + dp[4][2] , dp[3][2] + dp[4][2] ) = MAX(27,22)=27	중간 MAX( dp[3][2] + dp[4][3] , dp[3][3] + dp[4][4] ) = MAX(26,25)=26	맨 오른쪽 dp[3][3] + dp[4][4] =24

 

이러한 탐색 과정을 바탕으로 다음과 같은 점화식을 얻을 수 있다.

• 맨 왼쪽 : dp[i][j] += dp[i-1][j]
• 중간 : dp[i][j] = MAX(dp[i-1][j-1]+dp[i][j], dp[i-1][j]+dp[i][j])
• 맨 오른쪽 : dp[i][j] += dp[i-1][j-1]

이를 적용하여, 프로그램을 구현하면 문제를 해결할 수 있다. 이러한 과정은 상향식이며, 7이 있는 root노드를 단말노드로 거꾸로 뒤집은 트리라고 생각하고 진행하면 된다.

 

정답 코드

# https://www.acmicpc.net/problem/1932
# 정수 삼각형
# dp

input=__import__('sys').stdin.readline

n=int(input())
dp=[[*map(int,input().split())] for _ in range(n)]

# 트리의 각 레벨 탐색(=행)
for i in range(1,n):
    # 해당 레벨의 노드들 탐색(=열)
    for j in range(i+1):
        if j==0: # 양쪽 끝 중 왼쪽
            dp[i][j]+=dp[i-1][j]
        elif j==i: # 양쪽 끝 중 오른쪽
            dp[i][j]+=dp[i-1][j-1]
        else: # 중간
            dp[i][j]=max(dp[i-1][j-1]+dp[i][j], dp[i-1][j]+dp[i][j])

print(max(dp[n-1])) # 트리의 마지막 레벨의 각 노드 비교