[ Programmers / 파이썬 ] 정수 삼각형

Dynamic Programming

 

풀이 1. (실패, 풀이 소요 시간 15분)

def solution(triangle):
    answer = 0
    h = len(triangle)
    dp = [[0]*i for i in range(1,h+1)]
    dp[0] = triangle[0]
    for i in range(1, h):
        for j in range(i):
            if j == 0:
                dp[i][j] = dp[i-1][j] + triangle[i][j]
            elif j == h:
                dp[i][j] = dp[i-1][j-1] + triangle[i][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
    answer = max(dp[h-1])                
    return answer

채점 결과
정확성: 50.0
효율성: 21.4
합계: 71.4 / 100.0

 

풀이 방법이 간단하게 보여서 바로 통과할 줄 알았는데 정확성, 효율성 모두 실패하는 부분이 있어서 너무 당황했다.

간만에 코딩테스트 문제를 푸는데 .. 음.. 다시 열심히 해야겠다는 동기 부여가 된다. 자만하지 말아유~

 

일단 효율성에서 실패 문구가 뜨는 것부터 생각해보기 위해

처음 풀이할 때는 그냥 넘겼던 시간복잡도 계산을 해보자.

 

h(500) * j(1~500)

= h * (h-1)/2

= O(h^2)

이고,

최대값으로 통일시키면 

= 500 * 500 = 250,000 * 9999(약 10,000) = 2,500,000,000 이니까 파이썬 효율성에 위배될 수 있는것?

이라고 생각했는데 사실 여기서 

각 dp연산마다 triangle을 더해주는 것, max값을 비교하는 것까지 하면 연산 횟수가 또 미묘하게 올라가는 듯.

 

그리고 애초에 정확성 테스트에서 틀려버림..!

1. 합이니까 사실 바로 해줘도 될 것 같은데? 무슨 말이냐면 매번 dp에 triangle을 더해줄 필요 없이 미리 저장해두고 위에서 거쳐온 값에서 비교 필요한 경우만 합산해주면 되겠다.. 싶음. 

 

 

풀이 2. (실패, 풀이 소요 시간 15분)

def solution(triangle):
    answer = 0
    h = len(triangle)
    for i in range(1, h):
        for j in range(i+1):
            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], triangle[i-1][j-1])
    answer = max(triangle[h-1])                
    return answer

 

채점 결과
정확성: 64.3
효율성: 35.7
합계: 100.0 / 100.0

 

호오..? 예상대로 고치니까 정답 처리되었다.

로직 자체는 간단한데 음.. 

 

전에 인풋 값을 직접 바꾸려고하다가 꼬인 적이 있어서 안전하게 DP배열을 따로 설정해주려 한 것이었다.

이번에는 또 그렇게 하니까 효율성이 안 좋아지네..? ㅎ.. 

 

계속 많이 풀면서 상황에 따라 어떤 방법이 가장 적절한 지 구분 가능하도록 잘 이해해하며 풀어나가고 감을 잡아야겠다. ㅠ