문제 정보
문제 정리
아버지는 원형 정원을 M개, 직선형 정원을 K개 가지고 있다. 각 정원에는 사이프러스 나무가 일정 간격으로 심겨져 있고, 서로 이웃한 두 사이프러스 나무 사이에는 항상 올리브 나무가 한 그루씩 심겨져 있다. 아버지는 아들에게 사이프러스 나무를 Q개 선택하면, 그 Q개의 사이프러스 나무와 그 나무들 사이에 있는 올리브 나무도 전부 준다는 말을 유언으로 남겼다. 원형 정원과 직선형 정원에서 연속한 사이프러스 구간들을 골라서 사이프러스 수가 정확히 Q가 되도록 해야 하고, 이때 얻을 수 있는 올리브 나무의 최대 개수를 구하는 것이 목표이다.
풀이
직관적으로 구현했더니 좀 복잡해졌다... 일단 정리해보자.
- 원형 정원에 사이프러스가 i그루 있을 때, 정원의 모든 사이프러스를 선택하면 올리브를 i그루 얻는다.
- 직선형 정원에 사이프러스가 j그루 있을 때, 정원의 모든 사이프러스를 선택하면 올리브를 j-1그루 얻는다.
따라서, 같은 수의 사이프러스를 쓴다고 할 때, 원형 정원을 선택하는 것이 직선 정원보다 무조건 이득이다.
- 무조건 원형 정원을 선택하는 것이 이득이므로, Q에 가깝게 원형 정원을 최대한 선택한다. (배낭DP)
- 원형 정원 각각을 물건으로 보고, 그 정원의 사이프러스 개수를 물건의 무게, Q를 배낭 용량으로 볼 경우, 올리브 나무의 개수를 최대화하면서 사이프러스 총합이 Q를 넘지 않도록 하는 배낭DP 문제가 된다.
- 남은 사이프러스는 선택하지 않은 원형 정원 + 직선형 정원 그리디하게 선택하면 된다. (역추적 + 그리디)
- 선택하지 않은 원형 정원을 따로 구해야 하므로 역추적을 통해 선택한 정원을 먼저 추출하는 과정이 필요하다.
이렇게 풀면 답이 짜잔 하고 나온다.
처음에 원형 정원을 배낭DP로 선택하고, 남은 건 대해 직선형 정원에서만 선택했더니 79%에서 WA를 받았다. 그래서 역추적 과정을 추가해 선택하지 않은 원형 정원까지 후보에 추가해서 선택했더니 AC가 나왔다. 분명 풀 때 DP, 그리디, 배낭 문제, 역추적, 정렬을 썼는데 다른 사람들 기여를 보니 역추적, 정렬을 쓴 사람은 아무도 없었다...
다른 사람의 풀이 정리
다른 사람들과 런타임도 많이 차이나길래 어디에서 그렇게 차이가 나나 하고 몇 명의 코드를 봤더니
- 원형 정원을 많이 쓴다고 해서 손해보는 경우는 없다. 하지만 직선형 정원은 쓸 때마다 올리브가 1그루씩 손해이다. 따라서, 원형 정원만 사용해서 Q그루를 채울 수 있는지 확인하고, 불가능한 경우 직선형 정원까지 사용해 채워주면 된다.
이게 핵심 로직이었다. 구체적인 알고리즘은 아래와 같다.
- Q <= 원형 정원의 사이프러스 : 원형 정원만으로 Q를 채울 수 있으니 직선형 정원은 선택X.
- 원형 정원 중 일부를 골라 총합이 Q가 되는지를 체크해주면 된다. (배낭DP)
- Q > 원형 정원의 사이프러스 : 원형 정원의 사이프러스는 전부 사용. 직선형 정원에서 일부 선택.
- 원형 정원은 전부 사용했으므로, 직선형 정원에서 올리브 개수를 최대화하면 된다. 선택한 직선형 정원의 개수가 늘어날수록 올리브 나무가 손해이므로, 정렬하여 가장 큰 직선형 정원부터 그리디하게 선택하여 계산하면 된다. (그리디)
아이디어가 좀 어렵다... 내 풀이든 다른 사람 풀이든 G2치곤 어려워 보였다.
코드
# 백준 2335
import io
input = io.BufferedReader(io.FileIO(0), 1<<18).readline
def solve(Q, M, tree, line):
# DP로 나무 제한 Q를 넘지 않는 최대 나무 수 계산
DP = [0] * (Q+1)
prevSum = [-1] * (Q+1)
prevIdx = [-1] * (Q+1)
DP[0] = 1
for i in range(M):
curW = tree[i]
for j in range(Q, curW-1, -1):
if DP[j] == 0 and DP[j-curW] == 1:
DP[j] = 1
prevSum[j] = j-curW
prevIdx[j] = i
# 정원을 선택하고 남은 나무의 수 계산
olive = 0
leftTree = Q
for i in range(Q, -1, -1):
if DP[i] == 1:
olive += i
leftTree -= i
break
# 선택한 정원 역추적
use = set()
cur = Q - leftTree
while cur != 0:
curI = prevIdx[cur]
use.add(curI)
cur = prevSum[cur]
# 선택되지 않은 정원 이랑에 추가
for i in range(M):
if i not in use:
line.append(tree[i])
# 남은 정원과 이랑에서 그리디하게 선택
if leftTree > 0:
line.sort(reverse=True)
for curL in line:
if curL < leftTree:
leftTree -= curL
olive += curL-1
else:
olive += leftTree-1
break
return olive
def main():
Q, M, K = map(int, input().split())
tree = list(map(int, input().split()))
line = list(map(int, input().split()))
print(solve(Q, M, tree, line))
main()
