[일반] 늅이 알고리즘 문제 도움!

[익명(220.118)]

문제는 이건데 이진탐색으로 접근해야 하는건 알겠는데 어뜨케 구간을 나눠야 할지 모르겠음....

[익명(110.70)]

n이랑 k 입력 범위가 어떻게 됨?

[익명(223.62)]

과제는 스스로 해야지

[ㅍㄱㅈ(121.134)]

이진탐색이 아닌것같은데?

[익명(220.118)]

1<=n<=5000 , 1<=k<= 10임

[익명(220.118)]

4시간동안 혼자 풀었는데 도저히 모르겠어서 아이디어만 좀 알려줘...ㅜㅜㅜ 코딩은 내가할게

[익명(59.24)]

이진탐색만 쳐도 구글에 구현코드 널렸을 거 같은데 검색해봄?

[시아닌(kimjg1119)]

파라메트릭 서치 맞고, 한 필경사가 담당할 수 있는 최대 페이지를 정해두고 greedy하게 가능한지 판별해주면 돼

[ㅍㄱㅈ(121.134)]

이걸 greedy하게 푼다고???? 되게 무섭게 푸는데... x1 - xn 까지를 sigma 1-i [xi] 으로 pre processing해두고, xi - xj 하면 xi~xj 까지 합이 나오게 되잖아 그럼 여기서 y[k-1] 어레이 만들어서, 분리되는 점 greedy search 해도 되고 일단 1~k 까지 정리해두고 가장 작은것만 한 스텝씩 뒤로미는 방식도 가능 할 것 같은데 후자는 정답일진 모르겠네

[ㅍㄱㅈ(121.134)]

가장 큰 애를 하나씩 줄여주는 방식 ㅇㅇ 이건 확실하지 않고 integral array 만들어서 greedy search 하는게 암튼 확실할듯. 이 정도 preprocessing 해두면 속도도 빠를거고

[0xrgb(0xrgb)]

파라메트릭으로 하라니까

[0xrgb(0xrgb)]

한 필경사가 적을 수 있는 제한을 정해두고 그냥 앞에서부터 가능한만큼 시키셈. 모두 다 적을 수 있으면 답은 그 제한 이하인거고 아니면 제한보다 큼

[ㅍㄱㅈ(121.134)]

0xrgb / 갤주형 그럼 제한을 줄이면서 계속 돌려야 되는거 아님?

[ㅍㄱㅈ(121.134)]

너무 오래걸리는거 아닌가..?

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(223.62)]

nlogn이라 오래안걸려

[메리체리(mrscherry)]

n k 범위 보면 원래의도는 n^2k dp인가보네

[ㅍㄱㅈ(121.134)]

저게 왜 n log n이지? binary search가 n까지라고 정해진게 아니잖아? 챕터당 몇장있는지에 대한 범위는 안줫는데 지금?

[ㅍㄱㅈ(121.134)]

머 그래봐야 엄청 오래걸리진 않겠네 ;;

[메리체리(mrscherry)]

nlogX인데 생각없이 nlogn으로 쓰게되는일이 많아서

[메리체리(mrscherry)]

k가 작으면 n+klognlogX로 할수도 있고

[익명(220.118)]

https://codeshare.io/5Xnqk8
이렇게 짜봤는데 결과값이 안나와... 뭔가 잘못된거임..?ㅜㅜ

[ㅍㄱㅈ(163.152)]

코드가 없어서 그래

[ㅍㄱㅈ(163.152)]

nk도 될 것 같은뎀... 짜볼게 한번

[ㅍㄱㅈ(163.152)]

한숨만 자구..