[백준] - 다이나믹프로그래밍 정수 삼각형

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제 입력 1 복사

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력 1 복사

30

 

---

 

위와 같이 삼각형 문제를 풀 때면 항상 input 을 어떻게 받는 것이 효율적일까에 대한 고민을 많이 한다. 

항상 아래와 같이 input 을 받았다.

그냥 2N + 1의 크기로 모든 array 를 받고, 말그대로 직관적으로 indexing 을 하는 것이다. 

 

하지만, 생각보다 위와 같이 푸는건 메모리도, 약간의 시간도 그리고 결정적으로 코딩을 하는데 정신적 로드가 크다. 

 

위와 같이 풀면 코드는 아래와 같다. 

import sys
input = sys.stdin.readline 

N = int(input())

tri = [[0] * (2*N+1) for _ in range(N)]

for i in range(N):
    tmp = list(map(int, input().split()))
    for j,c in enumerate(tmp):
        tri[i][N-(i)+j*2] = c 

for i in range(1, N):
    for j in range(N-(i), N+(i+1), 2):
            tri[i][j] = tri[i][j] + max(tri[i-1][j-1], tri[i-1][j+1])


print(max([max(i) for i in tri]))

 

나쁜 코드는 아니다. 직관적이다. 하지만 위 코드를 자세히보면 생각보다 인덱싱이 좀 까다로운 것을 알 수 있다. 

 

N = int(input())
dp = []

for i in range(N):
    dp.append(list(map(int, input().split())))

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

print(max(dp[-1]))

하지만 위와 같이 array를 만들지 않아도 index 를 벗어날 경우를 예외 처리하고, 왼쪽 위, 오른쪽 위 index 를 접근하는 것이 각각 current x 좌표 -1, current x 좌표 라는 것을 알면 더 간단하게 코딩하고 정신적 로드도 훨씬 덜하다. 

심지어 메모리도 아끼고, 속도도 빠르다.