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에 저장시켜주면 된다.