[BOJ/백준] 1126 같은 탑

def solution(ind,diff):
    if diff > 250000:
        return -INF
    if ind == N:
        if diff == 0:
            return 0
        else:
            return -INF
    if dp[ind][diff] != -1:
        return dp[ind][diff]

    dp[ind][diff] = solution(ind+1,diff+arr[ind])
    dp[ind][diff] = max(dp[ind][diff],solution(ind+1,diff))
    if arr[ind] > diff:
        dp[ind][diff] = max(dp[ind][diff],diff + solution(ind+1,arr[ind]-diff))
    else:
        dp[ind][diff] = max(dp[ind][diff],arr[ind] + solution(ind+1,diff-arr[ind]))
    return dp[ind][diff]

N = int(input())
arr = list(map(int,input().split()))
arr = arr + [0]
INF = float('inf')
dp = [[-1] * 500001 for _ in range(N+1)]

result = solution(0,0)
if result == 0:
    print(-1)
else:
    print(result)

 

힘들게 풀었던 문제이다.

 

dp의 테이블에서 행은 현재의 index를 말하며, 열은 두 탑의 격차의 절대값을 말한다.

 

재귀함수를 통해 짰는데.

 

첫번째 : 해당 블록을 높이가 더 높은 쪽에 놓았을때,

 

두번째 : 해당 블록을 놓지 않았을때

 

세번째 : 높이가 낮은 블록에 놓았을 때 : 이 때 주의해야할 것은 현재 공통적으로 쌓아올려진 높이는 diff와 arr[ind]의 두 크기 중 작은 것에 된다.

 

이렇게 3가지 경우로 나뉘며, 세번째에는 격차가 클때와 현재 블록이 클때로 나뉘어서 된다.

 

 

이렇게 재귀를 하면서 마지막에서 들어온 diff가 0이면 높이가 같은것이므로 0을 반환해주고, 그게 아니면 두 높이가 다른것이므로, -INF를 반환해준다.

 

 

이게 내 첫번째 풀이였고, 실행시간은 3900ms로 엄청 느렸다.

 

그래서 다른 사람 풀이를 보고 공부한 코드는 다음과 같다.

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int,input().split()))

if N == 1:
    print(-1)
else:
    total_sum = sum(arr)
    dp = [[-1] * total_sum for _ in range(N)]
    dp[0][0] = 0
    dp[0][arr[0]] = arr[0]
    for ind in range(N-1):
        for j in range(total_sum//2+1):
            if dp[ind][j] != -1:
                # 다음 거의 블록을 쓰지 않을때
                dp[ind+1][j] = max(dp[ind][j],dp[ind+1][j])
                # 두 탑 중 더 높은 탑쪽에 블록을 쌓을때
                if j + arr[ind+1] < total_sum:
                    dp[ind+1][j+arr[ind+1]] = max(dp[ind+1][j+arr[ind+1]],dp[ind][j]+arr[ind+1])
                # 더 낮은 탑 쪽에 쌓는데 새로 쌓는 블록이 기존 블록보다 높을때 와 아닐때
                if arr[ind+1] > j:
                    dp[ind+1][arr[ind+1]-j] = max(dp[ind+1][arr[ind+1]-j],dp[ind][j] + arr[ind+1]-j)
                else:
                    dp[ind+1][j-arr[ind+1]] = max(dp[ind+1][j-arr[ind+1]],dp[ind][j])
    if dp[-1][0] == 0:
        print(-1)
    else:
        print(dp[-1][0])

 

 

위와 dp 테이블은 동일하다. 그런데 전체 input의 합을 구하고, 그거의 반만큼만 반복을 돌리도록 했다.

 

그래서 위에서는 재귀를 통해서 돌아가다 보니, 무조건 3개의 함수가 실행되다보니 밑의 코드보다 훨씬 오래걸린다.

 

밑의 코드는 50*250000이 최대 횟수로 볼수 있으므로, 위의 것보다 연산량에 이득을 본것 같다.

 

여기도 위와 비슷하게,

 

아무것도 놓지 않았을때

두 탑 중 더 높은 탑쪽에 쌓았을때,

두 탑 중 더 낮은 탑쪽에 쌓았을때,

 

를 구분해서 놓으면 된다.

 

그리고 dp에 저장되는 값은 해당 index에서 두 탑의 높이가 diff만큼 차이가 날때, 그때 더 높은탑의 크기를 저장해놓는 것이므로,

 

그것을 잘 구분해서, dp에 저장시켜주면 된다.