[문제 풀이] 정수 삼각형

코딩테스트 연습 - 정수 삼각형

 

해결 과정

DP의 BottomUp 방식으로 해결했다. 

triangle을 그대로 dp로 가져왔고, 초깃값 tirangle[0][0]은 값을 따로 넣어줄 필요 없이 그대로 사용하면 되므로, 이에 대한 코드가 없다. for문은 초깃값을 제외하고 그 다음부터 탐색한다. for i in range(1, len(dp))

 

나의 풀이

def solution(triangle):
    dp = triangle[:]

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

    return max(dp[len(dp)-1])

 

다른 풀이

다른 풀이도 비슷하다.

 

IDEA

DP 문제를 풀기 위해 접한 문제. DP는 결국, 모두 탐색하되, 이전에 한 번 계산해놓은 것을 다시 사용해야 하는 일이 있을 때, 이전에 저장해둔 결과값을 활용하는 것이다. 공간을 조금 더 쓰되, 시간 효율성을 추구하는 방식이라 볼 수 있겠다.