[BOJ] 1932 - 정수 삼각형

[BOJ] 1932 - 정수 삼각형

문제

문제

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

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

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

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

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

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

예제 입력

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

예제 출력

30

문제 해결

DP 문제이다. 일단 이차원 배열을 만들어 입력받은 요소들을 넣은 다음에 요소들을 순회한다. 일단 만들어 낼 수 있는 조건은

n (단, n > 1)단계에서 
1. 만약 0번쨰 값이라면 최대값은 n-1 단계의 0번쨰 값과 현재 인덱스 값 더하기
2. 만약 마지막 값이라면 최대값은 n-1 단계의 해당 인덱스의 값과 현재 인덱스 값 더하기
3. 위에 조건이 아니라면 최대값은 해당 인덱스와 인덱스-1 의 값중 큰 값과 현재 인덱스 값 더하기
4. 마지막으로 마지막 단계의 수중 가장 큰 값 리턴

크기가 3인 삼각형을 예로 설명해 보겠다.

우선 2차원 배열에 넣으면

1단계는 건너뛰고 생각하겠다.

2단계에서 0번째 인덱스라면 1단계의 0번쨰 인덱스 값과 더한다.

2단계에서 마지막 인덱스라면 1단계의 마지막 인덱스-1 값과 더한다.

위의 조건이 아니라면 1단계의 현재 인덱스와 현재 인덱스-1의 인덱스중 큰 값과 현재 인덱스의 값을 더한다.

나머지는 위에 있는 규칙대로 하면 된다. 코드로 구현해보자.

python 코드

n = int(input())
arr = []
ret = 0

for i in range(0, n):
    arr.append(list(map(int, input().split())))

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

for i in range(1, n):
    temp = max(arr[n-1][i-1], arr[n-1][i])
    if ret < temp:
        ret = temp

print(ret)

느낀점

그래도 RGB 거리를 풀었던 직후여서 그런지 좀 더 쉽게 접근할 수 있었다.