[일반] 피붕이 알고강의 과제 빡세네 하..

[익명(106.101)]

걍 푸념글임

정수 배열 적절히 절반으로 나눠서 두 서브배열의 각각의 합의 차이를 최소화 시키도록 서브배열 만드는 알고리즘 작성해오라는데

그리디로는 딱봐도 무리고

다이나믹이나 아니면 이분탐색인가? 분할정복인가? 존나 고민해도 답 안나옴

걍 바로 구글링 때림 -> tug of war 라는 존나 유명한 문제임

근데 이걸 또 정당성 서술하고 시간복잡도 계산과정 보이고 하려니깐 휴학 존나 마렵다

이거 원래 어려운문제 맞는거지?

[EN_SA(encludingsalt)]

당장 O(2^n)밖에 생각안나는데

[EN_SA(encludingsalt)]

얼마까지 깎아야함

[EN_SA(encludingsalt)]

아 혹시 양쪽 배열 크기는 달라도 됨? 합만 중요?

[익명(106.101)]

배열 크기 편의상 짝수로 가정하라는 조건이 딸려있음 반드시 반띵으로 나눠야함

[익명(106.101)]

근데 문제 다시보니깐 시간복잡도 바운더리는 딱히 없네 걍 시복 ㅈㄴ커져도 되니깐 해만 구해보란것같음

[EN_SA(encludingsalt)]

sum이 크지 않다면 knapsack으로 O(sum*n²)도? 이거 맞나 아님 아쉽고

[EN_SA(encludingsalt)]

ㅁㄹ

[익명(106.101)]

냅색 쓰면 O(sum*n^2) 맞다고 하더라

[익명(125.131)]

슈벌 O(n)인줄 알고 ㅈㄴ고민했네 - dc App

[익명(114.202)]

단순하게 보자면 분할정복으로 푸는거 아니냐? 배열을 좁혀서 합의 차이를 최소화 하라고 했으니까

[EN_SA(encludingsalt)]

ㅁㄹ

[익명(211.41)]

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

[무구정광대다라니경(woaldudrl)]

그냥 전형적 dp문제네

[익명(211.209)]

이거 비슷한 문제 풀어봤는데 냅색이었던 걸로 기억