[BOJ] 1932 : 정수 삼각형 [다이나믹 프로그래밍](Python)

문제 링크

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

1932번: 정수 삼각형

소스 코드

import sys

def main():
    n = int(sys.stdin.readline().strip())
    
    graph = []
    dp = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        graph.append(list(map(int,sys.stdin.readline().strip().split())))
    dp[0][0] = graph[0][0] # 맨 처음값

    if n == 1: # 한 개면 바로 종료
        print(dp[0][0])
        exit(0)
    elif n == 2: # 두 개도 바로 종료
        print(dp[0][0] + max(graph[1]))
        exit(0)
    
    # 두 번째 행까지 초기화
    dp[1][0],dp[1][1] = (dp[0][0]+graph[1][0]),(dp[0][0]+graph[1][1])
    for i in range(2,n): # 세 번째 행부터
        for j in range(i+1): # 3,4,5,..개를 확인
            if j == 0: # 첫 번째 열
                dp[i][j] = graph[i][j] + dp[i-1][j]
            elif j == i: # 중간인 경우
                dp[i][j] = graph[i][j] + dp[i-1][j-1]
            else: # 마지막 열
                dp[i][j] = max(graph[i][j]+dp[i-1][j-1],graph[i][j]+dp[i-1][j])
    
    print(max(dp[-1]))

if __name__ == "__main__":
    main()

 

해설

• 다이나믹 프로그래밍, dp

별 생각하지 않고 문제를 풀이하니 상당히 지저분한 코드가 되었습니다...

정석적인 풀이를 생각해보면 훨씬 깔끔하게 정리가 가능할텐데요..

 

우선 문제를 보는 순간 다이나믹 프로그래밍 유형임을 파악하기는 쉽습니다.

각 행에서 최선의 조건을 선택하며 마지막까지 쭉 내려간다면, 마지막 행의 최댓값이 곧 정답이 될 테니까요!

하지만 우리는 일반적으로 리스트로 입력을 받기 때문에 인덱스에 대해 잘 고민해봐야 합니다.

 

말이 삼각형이지 실제로는

1

2 3

4 5 6

이런 식으로 생겼잖아요?

 

사실

0

0 0

0 0 0

으로 그래프를 초기화해서 풀이하는 것이 가장 좋았을텐데(시간적으로나 메모리적으로나),

풀이할 당시에는 생각이 나지 않았습니다...

 

그래서 

0 0 0

0 0 0

0 0 0

이렇게 초기화를 해두고, 대신

 

1 0 0

1 1 0

1 1 1

1로 표시한 부분만 이중 for문으로 탐색하도록 한 것입니다.

 

두 내용을 코드로 비교하면 다음과 같습니다.

# 좋은 예
dp = []
for i in range(n):
	dp.append([0]*(i+1))

# 나쁜 예
dp = [[0 for _ in range(n)] for _ in range(n)]

(더 좋은 풀이에서는 dp 테이블을 따로 생성하지 않고 바로 값을 변경하면서 풀어서 메모리 효율성을 더 높인 것도 있습니다)

 

또 개선할만한 부분은..

이중 for문 중 첫 번째 for문의 범위를 굳이 저렇게 설정안하고 `for i in range(n)`으로 했어도.. 되겠네요.

그러면 굳이 n이 1일 때, 2일 때를 나누지 않고 바로 값을 업데이트 할 수 있습니다.

 

어쨌든 논리에 대해 간단히 설명하면,

1) 맨 앞, 맨 뒤의 숫자는 바로 위의 숫자와 더한다.

예를 들어

1

2 3

4 5 6

이 있을 때, 4와 6은 양 끝의 숫자라서 다른 값을 비교할 여지가 없습니다.

따라서 각각 2와 3에 저장된 최댓값과 더해주면 됩니다.

if j == 0: # 첫 번째 열
    dp[i][j] = graph[i][j] + dp[i-1][j]
elif j == i: # 중간인 경우
    dp[i][j] = graph[i][j] + dp[i-1][j-1]

 

2) 중간 숫자라면 '바로 위' vs '바로 위의 왼쪽'

위 예시에서 5를 본다면, 2와 3에 저장된 값 중 더 큰 것을 5와 더하여 5의 자리를 업데이트 해줘야합니다.

이때 2는 5보다 인덱스가 하나 작고, 3은 동일하므로 max 함수를 통해 두 값을 비교해줍니다.

dp[i][j] = max(graph[i][j]+dp[i-1][j-1],graph[i][j]+dp[i-1][j])

 

작업이 끝나면 마지막 행에서 가장 큰 값을 출력하면 됩니다!