BOJ 1126(같은 탑)풀이

 

https://www.acmicpc.net/problem/1126

1126번: 같은 탑

처음에 봤을 땐 그리디로 큰 값부터 작은 위치에 값을 더하는 방식으로 하고 싶지만 그러면 틀리게 된다.

이 문제는 dp 문제인데 i번째 블록을 움직일 수 있는 경우는 왼쪽 탑에 올린다, 오른쪽 탑에 올린다, 버린다

이렇게 3가지의 경우가 있다. 이때 왼쪽 탑과 오른쪽 탑으로 분리하지 말고 왼쪽 탑과 오른쪽 탑과의 높이 차로 dp 테이블을 만들 수 있다.

그럼 이렇게 정의하자 dp [i][j]=i부터 n까지 높이차가 j일 때 최대 높이

이제 테이블을 구현해보자 i번째에서 사용하지 않는 경우인 dp [i+1][j]와 높은 쪽에 올리는 경우 dp [i+1][j+input [i]], 낮은 곳에 올리는 경우 dp [i+1][abs(input [i]-j)]+min(input [i], j) 3가지를 이렇게 구현할 수 있다. 이때 낮은 곳에 올리는 경우에서 +min(input [i], j)를 추가한 이유는 최대 높이를 구해야 되기 때문에 낮은 높이에 올린 값을 더하기 위해서이다. 또 높은 곳에 올리는 경우일 때 더하지 않은 이유는 높은 곳에 올리면 i+1번째에서 낮은 곳에 올릴 때 최대 값을 만들 수 있기 때문에 더하지 않는다.

이제 이 모든 값들중 가장 큰 값을 저장하면 된다.

즉 dp[i][j]=max([dp[i+1][j],dp[i+1][j+input[i]],dp[i+1][abs(input[i]-j)]+min(input[i],j)]) 이 된다.

이때 dp[0][0]이 0일 경우 만들 수 없는 것이기 때문에 -1을 출력하면 된다.

import sys,math
inf=math.inf
input=sys.stdin.readline
a=int(input())
l=list(map(int,input().split()))
dp=[[-1 for g in range(500002)] for i in range(a+1)]
if a==1:print(-1);sys.exit()
if a==2:
    if l[0]==l[1]:print(l[0])
    else:print(-1)
    sys.exit()
for i in range(a,-1,-1):
    for j in range(500002):
        if j==500001:dp[i][j]=-inf
        if i==a:
            if j==0:dp[i][j]=0
            else:dp[i][j]=-inf
        else:
            dp[i][j]=max([dp[i+1][j],dp[i+1][min(500001,j+l[i])],dp[i+1][abs(l[i]-j)]+min(l[i],j)])
ans=dp[0][0]
print('-1'if ans==0 else ans)