[일반] 애미 시발 밑에 15673 dp 문제 풀었다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

[익명(221.163)]

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

와 진짜 내가 이걸 풀 수 있을 줄 몰랐다. 

어제 저녁에 하루종일 고민해도 못 풀어서 걍 자고 일어났는데 갑자기 번뜩! 하더니 풀이가 떠오름.

기대반 걱정반으로 제출했는데 퍼센트 쭉쭉 올라가면서 맞았습니다 캬.... 진심 소름 돋고 전율이 올랐다.

내 한계를 돌파한 느낌이 들었음.

-- 힌트 --

dp 문제의 바이블인 연속하는 구간합의 최대, 최소값을 응용해라

[익명(14.36)]

ㅅㅂ 글쓴인데 아직도 안풀림

[익명(221.163)]

힌트 봐도?

[익명(14.36)]

ㅇㅇ

[익명(14.36)]

사실 최대최소 관찰은 처음부터 해봤지.. 그냥 머리가 딸리는 듯 시발.

[익명(221.163)]

그럼 곧 풀겠는데?

[익명(14.36)]

질문점 1) 역순으로 누적합 안구해도 되냐? 2) dp처럼 숫자가 2개일 때 누적합 최대최소, 3개일 때 누적합 최대최소, 4개일 때 누적합 최대최소 이렇게 하는거 맞음?

[익명(221.163)]

1. 구해야함 2. 좀 다름

[익명(14.36)]

ㄳㄳ 저녁까지 해봄

[익명(221.163)]

진짜 다 왔음. 2번을 좀 간소화해보삼

[익명(14.36)]

ㅈㅈ 하

[익명(221.163)]

지금 상황이 어떤데?

[익명(211.243)]

걍 진전이 없음 -10 4 -5 8 -9 -10 -6 -11 -3 -12 -12 -2 -6 -1 -9 누적합 정순 역순만 하염없이 바라보는 중 ㅋㅋ..

[익명(221.163)]

누적합이 아니야. dp로 푸는 거임. dp[i] = i번째 인덱스를 끝으로 뒀을 때 최대 누적합을 정순, 역순해봐라

[익명(14.36)]

나 시간초과 났는데 한번 봐줄 수 있어? 백준 채점현황에 있어