초록책 보다가 maximum subarray 문제가 나와가지고
실버3에 부분배열 합 최대로 만드는 기본문제 가볍게 풀어주고
그 다음 도전문제를 검색했는데 저 문제가 나왔어요
부분배열의 합에다가 최소 원소를 곱하는 게 들어가서 까다로워 보였지만
재밌을거 같았어요 그리고 O(n)으로 풀어야 되니까 배열 입력과 동시에 그 부분까지의 최대값을 업데이트하는 로직을 만들면 되겠지! 라고 생각하며 구현을 시작했어요
최소 원소가 바뀌면 봐야 되는 부분 배열의 경우의 수가 늘어나니까 DP인가 생각을 하면서 이것저것 배열에 저장을 시켰어요

문제 풀기 시작한 게 코포 치기 1시간 전이었는데
코포 시작 10분전쯤에 첫 틀렸습니다를 받았어요
이대로 넘어가기엔 찝찝해서 그냥 코포를 제끼고 문제를 계속 풀기로 했습니다
디피로 풀다보니까 점화식도 제대로 안세운것을 깨달아서 (기초 부족)
재귀로 짜 보기도 하고 여러 시도를 해본거 같아요
계속 하다보니까 조금씩 실마리가 보이는 것 같았어요

결과값을 ll이 아닌 int에 저장한 걸 깨닫는 순간 틀렸습니다는 시간초과로 바뀌어 있었어요
그때부터 최대한 머리를 굴려서 할 수 있는 최적화는 다 해봤지만
입력에 1부터 10만까지를 순서대로 넣는 걸 시켜보니 제가 짠 로직으론 어떻게 해도 O(n)에 근접하게 갈 수가 없드라구요

도무지 지금 지식으로는 힘들겠다 싶어서 초록책 보던 부분에서 조금 뒤로 가서 누적합 부분을 슬쩍 엿봤어요
그러다 눈에 띈 키워드 ‘스택’

그때 예제 입력을 제가 기존에 짠 로직에 맞춰 대강 그려봤는데
생각해보니 계산값 여러개를 계속 업데이트할 필요 없이 스택을 쓰면서 맨 위 부분배열 하나만 관리해도 되겠더라고요??
그래서 곧바로 코드를 다 엎고 새 구현에 들어갔고
사소한 실수로 틀렸습니다를 두번 더 받긴 했지만 8시간 만에 맞았습니다를 받을 수 있었읍니다..

그간 실버와 골드 문제들을 풀면서 기본기를 다져왔다고 생각하지만 플래티넘 문제는 저에게 엄청 넘기 어려운 벽으로 남아있었는데
오늘 잠안자고 코포도 거르고 이 문제를 푼 덕에 꽤 내적인 성장을 할 수 있을 것 같아요
PS를 만나고 내 인생이 달라졌다. 진짜에요 앞으로도 열심히 해보겠습니다!