글 읽기 - 약 봉지의 수를 최소로 하는 알고리즘은 없을까요

jdown 6년 전 3

입력값에 상관없이

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

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

doju 6년 전 11

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

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

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

약봉지 1개 : 최대 1개까지 전부 줄 수 있음
[ 1 ]
약봉지 2개 : 최대 3개까지 전부 줄 수 있음
[ 1 2 ]
약봉지 3개 : 최대 6개까지 전부 줄 수 있음
[ 1 3 2 ]
약봉지 4개 : 최대 9개까지 전부 줄 수 있음
[ 1 1 4 3 ], [ 1 3 3 2 ], [ 2 5 1 3 ], [ 4 1 2 6 ]
약봉지 5개 : 최대 13개까지 전부 줄 수 있음
[ 1 1 4 4 3 ], [ 1 3 1 6 2 ], [ 1 5 3 2 2 ] 등 7가지
약봉지 6개 : 최대 18개까지 전부 줄 수 있음
[ 2 5 7 1 3 6 ], [ 2 5 6 3 1 8 ], [ 5 2 6 3 1 14 ], [ 6 4 5 2 1 13 ]
약봉지 7개 : 최대 24개까지 전부 줄 수 있음
[ 8 7 2 3 1 10 8 ]
약봉지 8개 : 최대 29개까지 전부 줄 수 있음
[ 1 1 12 4 3 3 3 2 ], [ 1 2 3 7 7 4 4 1 ], [ 1 3 6 6 6 2 3 2 ] 등 15가지

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

문제

문제

출처

ICPC

약 봉지의 수를 최소로 하는 알고리즘은 없을까요

jdown 6년 전 3

doju 6년 전 11

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말