문제
내가 좋아하는했던 DP 문제!
문제도 간단해서 구현하기 어렵지 않을 것이라 생각했는데...
너무나도 경기도 오산⛰
그리고 알고리즘 분류를 안 봤더라면 DP인 줄 몰랐을 것 같긴 하다.
심지어 풀다보니 DP로 안 풀고 있었다.
(틀린) 풀이
틀렸습니다!
import sys
input = sys.stdin.readline
def shorten(count):
stack = []
isAllNegative = True
negativeList = []
for i in range(count):
todayRevenue = int(input())
isAllNegative = todayRevenue < 0
isNegative = todayRevenue < 0
if not isAllNegative:
pass
else:
negativeList.append(todayRevenue)
if i == 0:
stack.append(todayRevenue)
continue
if stack[-1] < 0:
if isNegative:
stack[-1] += todayRevenue
else:
stack.append(todayRevenue)
else:
if isNegative:
stack.append(todayRevenue)
else:
stack[-1] += todayRevenue
if len(negativeList) == count:
return negativeList
# [-1000, -19]
return stack
# [-3, 13, -7, 8]
def sumMax(revenueList):
tempMax = max(revenueList)
revenueList = revenueList + [0, 0]
answerStack = []
if revenueList[0] < 0:
revenueList.pop(0)
length = len(revenueList) -2
for i in range(1, length, 2):
if i == length-1 or i == length:
answerStack.append(revenueList[i-1])
break
if revenueList[i-1] + revenueList[i+1] > abs(revenueList[i]):
answerStack.append(revenueList[i-1] + revenueList[i])
return max(tempMax, sum(answerStack))
# [ 2 -18 8 -29 8 -1 19 -3]
while True:
testCaseCount = int(input())
if testCaseCount == 0:
exit()
shortenList = shorten(testCaseCount)
if max(shortenList) < 0:
print(max(shortenList))
else:
print(sumMax(shortenList))
# 도저히 반례를 못 찾겠어..
while문에서 각 테스트케이스를 받고 바로 답을 출력한다.
여기서 먼저 전일 수익 내역을 shorten()에 넣는다.
이 함수가 하는 역할은 다음 설명에서 이어진다.
최대 수익을 내는 구간에 해당하는 '수익'을 출력하면 된다.
여기서 구간에 대한 정보는 무의미해지고,
최대 수익을 낸다고 하면, 이익을 내는 구간 중간에 구간의 시작과 끝이 될 수 없고, 더불어 손해를 내는 구간 중간에 구간의 시작과 끝이 될 수 없다.
ex.
...3 9 18 -13 12 -11 -19 -3 12 18...
...3 9 18 / -13 / 12 / -11 -19 -3 / 12 18...
👆 👆
...3 9 18 / -13 / 12 / -11 -19 -3 / 12 18...
👆 👆
위처럼 같은 부호로 구분되는 와중에 구간이 정해질 리 없다.
따라서 같은 부호가 이어지는 구간을 하나로 합치는 작업을 하기 위해 shorten()을 만들었다.
다소 길긴하지만, 완전탐색으로 하나씩 가면서 이전의 부호와 달라지면 이전에 합쳤던 것을 새로운 배열에 넣는 것이 핵심이다.
또한 문제 조건 상 전체 손익 배열이 손해뿐일 때, 그나마 가장 적은 손해를 뽑아야 하므로 shorten()에서 이 조건에 해당하는 경우는 배열 그대로를 빼도록 처리했다.
isAllNegative = todayRevenue < 0
isNegative = todayRevenue < 0
if not isAllNegative:
pass
else:
negativeList.append(todayRevenue)(javascript 냄새 폴폴 나는 코드)
그 다음에는 sumMax()인데 로직은 다음과 같다.
shorten()의 결과값은 항상 +, -의 반복이다.
따라서 - 양쪽의 + 값이 있을 때, 세 손익의 합이 양수라면 중간에 낀 음수값을 안고 가는 것이 최대 손익합을 구하는 것이다.
당연히 해당 음수값을 안고간다는 판단이 서면 다음 양수값은 자연스럽게 더해지게 된다.
여러 반례들을 넣고 해당 경우에 대한 것을 커버해도 틀렸습니다가 떠서 몹시 슬펐다...
그래서 결국 맞았습니다!를 얻지 못하고 스터디를 진행했는데,
생각보다 DP로 푸는 데 너무나도 간단하게 나와서
정말 허무했다.
나는 70줄이 넘어가는데 다른 분들은 15줄이면 끝!
풀이
47116KB ⭐️720ms⭐️
import sys
input = sys.stdin.readline
# 양수는 양수끼리, 음수는 음수끼리 묶어서 미리 더해버리기
def shorten(count):
stack = []
isAllNegative = True
negativeList = []
for i in range(count):
todayRevenue = int(input())
isAllNegative = todayRevenue < 0
isNegative = todayRevenue < 0
# 모든 수익이 음수인 경우(왜 사업을 안 접는지 의문)
# 합치면 안되므로 한 곳에 미리 저장해두기
if not isAllNegative:
pass
else:
negativeList.append(todayRevenue)
# 처음에는 넣기만 하기
if i == 0:
stack.append(todayRevenue)
continue
# 이전의 것과 현재의 것의 음양을 비교해 넣기
if stack[-1] < 0:
if isNegative:
stack[-1] += todayRevenue
else:
stack.append(todayRevenue)
else:
if isNegative:
stack.append(todayRevenue)
else:
stack[-1] += todayRevenue
# 음수만 있는 경우
if len(negativeList) == count:
return negativeList
return stack
while True:
testCaseCount = int(input())
if testCaseCount == 0:
exit()
# 수익들 음양으로 묶어서 압축시키기
shortenList = shorten(testCaseCount)
# 음수만 있는 경우
if max(shortenList) < 0:
print(max(shortenList))
else:
# 압축시킨 수열로다가 DP 처리 하기
for i in range(1, len(shortenList)):
if shortenList[i-1] + shortenList[i] > shortenList[i]:
shortenList[i] = shortenList[i-1] + shortenList[i]
print(max(shortenList))
나도 다른 분들처럼 간단하게 DP로 풀고 제출하려 했는데, 앞서 짠 shorten()이 너무 마음에 들어서 갖고 갔다.
DP 핵심은 단 세 줄
for i in range(1, len(shortenList)):
if shortenList[i-1] + shortenList[i] > shortenList[i]:
shortenList[i] = shortenList[i-1] + shortenList[i]
print(max(shortenList))축약된 결과값들을 처음부터 훑으면서 총합의 최댓값을 구간 마지막에 업데이트하는 것이다!
이전 구간부터 더했던 것과 현재 인덱스의 그것과 비교해서 현재 인덱스가 더 크면 그대로 유지하며 해당 인덱스부터 새롭게 최댓값 구간이 시작되는 것이다.
사실 처음에 이렇게 할까 생각했는데,
왜인지 모르게 중간부터 시작하는 구간을 커버하지 못할 것이라는 판단을 했었다.🤔
정말 점화식만 잘 세우면 끝나는 DP인데... 뭔가 아까워!
그래도 최근에 이렇게까지 붙잡고 풀려고 한 문제가 없었는데
시간을 할애해서 멱살 잡히는 경험... 나쁘지 않다!
더불어서 그냥 DP로 한 것보다 한 번 shorten()를 거친 내 코드가 비교적 빠르다!
앞서 노력했던 것에 대한 보상을 이렇게 시간복잡도 줄인 것으로 받은 느낌이다.
