[BOJ] 1932.정수삼각형

 

문제 소개

 

 

 

 

DFS

 

맨 아랫줄까지 제한된 방향 수의 연산을 반복적으로 실행해야 될 것으로 파악되어 재귀적인 방법을 떠올렸다.

가능한 모든 경우의 수를 살펴보고자 DFS로의 접근을 시도하였다.

 

def dfs(i, j, total_sum):
    if i == test_cases - 1:
        total_sum = max(total_sum, arr[i][j])
    else:
        left = dfs(i + 1, j, total_sum)
        right = dfs(i + 1, j + 1, total_sum)

        route1 = arr[i][j] + left + total_sum
        route2 = arr[i][j] + right + total_sum

        total_sum = max(route1, route2)
        
    return total_sum

test_cases = int(input())
arr = []
for _ in range(test_cases):
    number = list(map(int, input().split()))
    arr.append(number)


result = dfs(0, 0, 0)
print(result)

 

 

 

위의 코드를 실행한 결과 작동 방식은 다음과 같다. 큰 틀에서 보자면 연산 순서는 표시된 바와 같다. 연산의 결과가 누적되며 갱신되는 총 합계 값에 대해서는 빨간색으로 표시하였다.

 

연산 과정은 아래와 같다.

 

1. 첫번째 연산은 마지막 줄 이전 줄의 각 숫자를 기준으로 이루어진다.
2. 하위 왼쪽 오른쪽 숫자 중에서 가장 큰 값을 선택하여 합계를 계산한다.
3. 각 두 그룹의 최대값 합계가 구해졌으면 상위 레벨의 숫자로 이동하여 다시 둘 중의 최대합계를 구한다. 이 때 왼쪽 오른쪽 숫자의 최대값을 구할 때에는 누적된 값으로 비교한다. 3번을 예로 들자면, 8을 기준으로 7과 12 둘 중 큰 숫자를 선택하여 합계를 갱신한다.
4. 꼭대기 레벨로 이동할 때까지 위 연산을 반복한다. 꼭대기 레벨에 이르게 되면 최대가 되는 경로에 있는 수의 합을 출력한다.

 

 

한계점

 

재귀연산으로 인해 비교와 연산이 중복적으로 일어나다보니 시간초과가 발생하였다. 생각해보면 연산의 최종 결과값은 누적되는 형태로 구해진다. Dynamic Programming을 공부했을 때 배운 메모이제이션(Memoization) 개념이 적용 가능한 문제라고 확신이 들었고, 더 나아가 연산의 결과값을 DP 테이블에 저장하고 그 값을 가져와서 아직 연산이 이루어지지 않은 숫자와 계산하여 최대값을 갱신하는 방식으로 구할 수 있을 것 같다는 생각이 떠올랐다.

 

 

 

DP 풀이

 

def findMaxPath(i, j):
    dp = [[-1] * test_cases for _ in range(len(arr))]
    
    for i in range(len(arr)):
        for j in range(i+1):
            dp[i][j] = arr[i][j]
            
            # 정수 삼각형의 꼭대기 레벨(0, 0)는 갱신할 dp 배열에서 제외
            if (0 == i == j):
                break
			
            # (i, 0)에 해당하는 숫자를 누적적으로 합하여 dp 배열을 갱신함.
            elif (j == 0):
                dp[i][j] = arr[i][j] + dp[i-1][j]

            # 배열에 정수 삼각형 숫자가 없는 경우
            elif (dp[i-1][j-1] != -1):
           		# 두 개의 숫자합 중에 더 큰 것으로 갱신
                dp[i][j] = max(arr[i][j] + dp[i-1][j],
                               arr[i][j] + dp[i-1][j-1])
                
    return max(dp[i])


test_cases = int(input())
arr = []
for _ in range(test_cases):
    number = list(map(int, input().split()))
    arr.append(number)

result = findMaxPath(0, 0)
print(result)

 

 

1. i행 0열에 위치한 숫자들을 누적적으로 합하여 테이블을 갱신한다.
2. [[8], [1, 0], [7, 4, 4], [5, 2, 6, 5]] 범위에서 각 행/열을 순회하며 dp[i-1][j]셀과 dp[i-1][j-1]셀 중, 더 큰 값을 비교하여 누적연산을 한다.
3. 각 셀의 연산이 완료된 이후, dp[i]번째 행에서 가장 큰 값을 반환한다.

 

위 풀이과정에 대해 그림으로 정리해보았다.

 

 

0번째 열의 누적합을 미리 계산해두어 순회 범위에서 제외시키고, 현재 셀을 기준으로 [i-1][j]셀과 [i-1][j-1]셀의 숫자 중 더 큰 것을 선택하여 현재 셀의 값을 갱신하는 방식으로 풀이하였다.