jdown   1년 전

입력값에 상관없이

최대값인 N=1000000일 때 임의로 만든 답안들이 통과되는거 보면 조건만 만족하면 통과인것같은데...


임의의 N에 대해 약 봉지의 수를 최소화하는 풀이법은 없을까요?

doju   1년 전

해당 문제는 Sparse ruler 문제의 일종으로 변형할 수 있습니다.

무한한 길이의 자에 정해진 개수만큼의 구분선을 그을 때, 최대 얼마까지의 길이를 전부 측정할 수 있는가?

다만 제 검색 능력이 부족한 것일 수도 있겠지만 다항시간에 해결하는 방법이 알려지지 않은 문제로 보입니다. 작은 범위에서의 답을 몇 개 첨부합니다.

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