zeikar   1년 전

모든 길이를 더한 후 N으로 나눈 값부터 모두 탐색하게 짰는데 역시나 시간초과가 뜨네요 ㅠㅠ

다른 방법으로 접근해야할거 같은데 감이 안오네요...

mastojun   1년 전

접근은 잘 하신거 같은데 탐색방법만 좀더 효율적으로 바꾸시면 될듯 합니다.

일단, 입력으로 주어지는 랜선의 길이의 입력범위는 주어지지 않았으므로 sum += lan[i]의 경우 overflow가 발생할 가능성이 있고요.

길이가 k 인 랜선으로 자를 때 그 갯수가 N개 이하라면 k 이상의 수는 정답 후보에서 제외됩니다.
길이가 k 인 랜선으로 자를 때 그 갯수가 N개 이상이라면 k 이상의 수 중에 답이 있습니다.

sum / N (sum overflow문제는 무시하더라도) 부터 0 까지 모두다 검사할 필요없이 중간지점을 검사해서 가능하면 그 위를/ 아니면 그 아래를 반복하면 됩니다.
이분법/bisection method 등을 찾아보세요, JMBook의 12장 최적화 문제 결정 문제로 바꿔 풀기 에도 잘 나와 있습니다 :)

zeikar   1년 전

이분법 비슷하게 해서 통과했습니다!

감사합니다.


알고리즘 참 어렵네요..ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.