[python] 백준 1932: 정수 삼각형

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

 

백준 1932번 정수 삼각형 문제이다. dp를 이용하여 풀 수도 있고, 이용하지 않고 메모리를 아끼면서 풀이도 가능하다.

 

 

1)다이나믹 프로그래밍(dp) 이용

# 백준 1932: 정수 삼각형

n = int(input())

triangle = []

# 삼각형 입력 받기

for _ in range(n):

triangle.append(list(map(int, input().split())))

# dp 배열 초기화

dp = [[0] * n for _ in range(n)]

dp[0][0] = triangle[0][0] # 첫 번째 값 입력

# dp 배열 업데이트

for i in range(1, n): # 1부터 시작 (0은 위에서 이미 입력했음)!!

for j in range(i + 1): # i+1까지만 돌면 됨

if j == 0: # 왼쪽 끝일 때

dp[i][j] = dp[i-1][j] + triangle[i][j] # 왼쪽 끝은 왼쪽 위에서만 옴

elif j == i: # 오른쪽 끝일 때

dp[i][j] = dp[i-1][j-1] + triangle[i][j] # 오른쪽 끝은 오른쪽 위에서만 옴

else: # 중간에 있을 때

dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] # 왼쪽 위, 오른쪽 위 중 큰 값 선택

# 최대 합 출력

print(max(dp[n-1]))

 

 

2) 리스트로 집어넣기

 

#백준 1932: 정수 삼각형

n = int(input())

triangle = []

#삼각형 입력받기

for _ in range(n):

triangle.append(list(map(int, input().split())))

 

#합 저장

for i in range(1, n):

for j in range(i+1): #왜 0부터 시작? -> 0부터 시작하는 이유는 삼각형의 맨 왼쪽과 맨 오른쪽은 이전 행의 값과만 더해지기 때문 !! 중요

if j == 0:

triangle[i][j] += triangle[i-1][j]

elif j == i:

triangle[i][j] += triangle[i-1][j-1]

else:

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

 

print(max(triangle[n-1]))

 

코드의 메모리 관리 측면에서는 dp를 이용하지 않는 게 낫다는 생각이다 (이유: 문제의 삼각형 크기가 500 이하라고 정해졌으므로, 그렇게 크지 않다고 판단하였다.)

 

그러나 n 개수가 무수히 커질수록, 다른 방법을 모색해야만 한다. 그러한 해결책으로서 다이나믹프로그래밍을 사용할 수 있다.

 

핵심 아이디어는 왼쪽 끝, 아래쪽 끝, 중간 부분을 따로 생각하여 if 문으로 처리한다는 점이다. 양쪽 끝의 삼각형들의 값은 그대로 양쪽 끝으로 받게 되어있다. 그러나 처음과 끝을 제외한 나머지 부분들은, dp이든 리스트든 맥시멈 값을 받아주어야 한다는 것에 착안, 코드를 구성해보았다.