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

 

첫번째행부터 자신의 위에서 나올 수 있는 최대값에 자신을 더하는 방식으로 문제를 풀어나갔다.

 

 

0번째열이라면 dp[i-1][j]+자기자신이 답이니 바로 저장하고

열값이 0보다 크다면 dp[i-1][j-1]과 dp[i-1][j]중 더 큰 값에 자기자신을 더한 걸 dp테이블에 저장하도록 했다.

 

n = int(input())

arr = [list(map(int,input().split())) for _ in range(n)]
dp = [[0]*n for _ in range(n)]
dp[0][0] = arr[0][0]

# 1부터 n-1행까지
for i in range(1,n):
	# 0 부터 i까지
    for j in range(i+1):
    	# 0번째 열이면 
        if j ==0:
            dp[i][j]=dp[i-1][j]+arr[i][j]
        else:
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+arr[i][j]

# 마지막 행 중 가장 큰 값이 최대값이 됨
print(max(dp[n-1]))

 

내 풀이가 그렇게 매끄럽진 않은 것 같아서 다른 풀이를 참고해봤다.

 

n = int(input())

arr = [list(map(int,input().split())) for _ in range(n)]

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

print(arr)

dp테이블을 따로 만들지 않고 삼각형값을 입력받은 리스트를 그대로 사용해서

메모리도 절약되고 코드도 짧아졌다.

무엇보다 반복문 조건도 더 직관적이고 깔끔해져서 이해하기 쉬워졌다.

 

정말 문제에서 요구한 대로 풀어낸 간단한 코드인데 왜 떠올리기가 어려웠을까?

아직 갈 길이 멀다