[프로그래머스] 파이썬 python 정수 삼각형 풀이

 

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

 

맨 위층 (7) 부터 시작하여 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램 작성. 

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

 

삼각형의 크기는 1 이상 500이하, 각 정수들의 범위는 0 이상 9999 이하

 

• 입력 조건 : 첫째 줄에 삼각형의 크기 n이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
• 출력 조건 : 합이 최대가 되는 경로에 있는 수의 합 출력

---

이 부분 챕터를 푸는 중이라 그런지 문제 보자마자 푸는 방법을 깨달아서 뿌듯했당 .. ㅎㅋ 

 

먼저, 계산한 값들을 저장할 새로운 배열을 만들어야 한다. (dp 테이블)

dp 테이블은 위에서부터 차례로 계산해준 값을 해당 자리에 저장해주는 역할이다.

예를 들어,

• dp 테이블의 첫째 줄 : 원래의 정수 삼각형의 첫째 줄인 7
• dp 테이블의 둘째 줄 :  10 (7+3) , 15 (7+8)
• dp 테이블의 셋째 줄 :  18 (7+3+8), max(7+3+1, 7+8+1), 15 (7+8+0)
• ... 

셋째 줄 부터 중요한데, 우선 양 끝은 그냥 선택할 것 없이 쭉 더해서 내려오면 된다. 그런데 중간에 낀 값들은 선택을 해줘야 한다. 여기서는 최댓값을 구하라고 했으니까 max 함수를 사용하여 선택해주면 된다. 

이렇게 dp 테이블의 마지막 줄까지 채운 다음, 마지막 줄의 최댓값을 구하면 문제의 해답이 된다.

 

그림으로 설명해보면 요런 느낌 ... 

이 내용을 코드로 구현하면 다음과 같다!

 

1. 변수 생성

n = int(input()) # 삼각형의 크기

array = []  # 정수 삼각형
for i in range(n):
    temp = list(map(int, input().split()))
    array.append(temp)

2. dp 테이블 생성 및 초기화(계산 저장용 리스트) : 우선 array와 똑같은 형태인 0으로 채워진 배열을 만든 후, 첫째 줄만 채워준다.

d = []
for i in range(n):
    d.append([0]*(i+1))
    
d[0][0] = array[0][0]

3. dp 테이블에 계산값 저장하기

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

차근차근보면 

먼저 j == 0 일 때는 수가 가장 왼쪽에 있을 때! 이 때는 전 줄의 왼쪽이 없기 때문에 그냥 전 줄의 같은 위치에 있는 값을 더해주면 된다.

j == i, 즉 가장 오른쪽 값일 때는 마찬가지로 , 전 줄의 오른쪽이 없기 때문에 전 줄의 마지막 값만 더해준다.

마지막으로 양 끝이 아닌 중간에 있을 때는 왼쪽 위를 선택할 것이냐, 오른쪽 위를 선택할 것이냐를 정해야 한다. 둘 중 최대값을 더해줘야 하므로 max값을 이용하여 큰 값을 더해준다.

 

이렇게 반복문을 모두 통과하고 나면 

 d = [[7], [10, 15], [18, 16, 15], [20, 25, 20, 19], [24, 30, 27, 26, 24]]

로 채워지게 되고, 정답은 d의 마지막 줄의 최댓값인 30이 된다.

 

<전체 코드>

n = int(input()) # 삼각형의 크기

array = []  # 정수 삼각형
for i in range(n):
    temp = list(map(int, input().split()))
    array.append(temp)
    
d = []
for i in range(n):
    d.append([0]*(i+1))
    
d[0][0] = array[0][0]

for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            d[i][j] = d[i-1][j] + array[i][j]
        elif j == i:
            d[i][j] = d[i-1][i-1] + array[i][j]
        else:
            d[i][j] = max(d[i-1][j-1], d[i-1][j]) + array[i][j]
            
# 정답 : 30
print(max(d[-1]))

이건 내가 생각해서 호다닥 짠 코드라.. 더 깔끔한 코드가 있을 수도 있지만 일단 만족 ...