i번째 진열대에는 무게가 F_i인 물건 하나가 놓여있다.(F_i는 i번째 피보나치 수,  F_0=1, F_1=2)

용량 W의 가방에 물건들을 담아 꽉 채울 수 있는 경우의 수를 구하라. 단, 진열대는 무한히 많고 물건은  쪼갤 수 없다.

 

풀이

제켄도르프 분해: 어떠한 자연수도 "연속하지 않는" 서로 다른 피보나치 수들의 합으로 나타낼 수 있으며, 그 경우는 유일하다.

문제의 요구사항: 위 내용에서 "연속하지 않는"이란 조건이 빠졌을때 경우의 수를 구하라.

관련있어보이므로 제켄도르프 분해에서 접근해보자. 자연수 N에 대해 제켄도르프 분해하여 i번째 피보나치 수가 사용되면 i번째 자리를 1, 아니면 0으로 하는 이진표현을 사용하면 편하다. 그냥 이진수와 혼동을 피하기 위해(이 글에서 이진수를 사용하지는 않지만) 아래첨자 _F를 붙이겠다. 또한 모든 피보나치 수가 서로 다르도록 F_0=1 F_1=2로 정의하겠다. ex) 12=8+3+1=F_4+F_2+F_0=10101_F

 

관찰#1

n번째 피보나치 수 F_n에 대해 제켄도르프 이진표현의 0의 개수가 n개이다.

 

관찰#2

n번째 피보나치 수 F_n에 대해 (01)^k10^(n-2k) where 0<=k<=floor(n/2) 형태의 정규식 문자열로만 표현이 가능하다.

F_0=1_F

F_1=10_F

F_2=100_F=011_F

F_3=1000_F=0110_F

F_4=10000_F=01100_F=01011_F

F_5=100000_F=011000_F=010110_F

 

관찰#3

K=0인경우 1로 시작하고, 그 외의 경우 01로 시작함을 기억하라. 뒤에서 0의 개수셀때 중요하게 사용된다.

 

n번째 피보나치 수의 0의 개수는 n개이므로, 이제부터는 0의 개수에 집중하는게 이해하기 쉽다. 위에서 한 관찰을 임의의 자연수로 일반화하기 위해, 자연수 N의 제켄도르프 분해 이진표현을 1과 그 오른쪽에 연속한 0들로 묶어 그룹을 나누자. 낮은 자리수부터 오름차순으로 인덱싱하자. 그룹i에 포함된 0의 개수는 b_i로 표현하겠다. ex) 100010100 => (그룹,idx,b_i){(1000,2,3),(10,1,1),(100,0,2)}

 

관찰#4 그룹 i에서 사용가능한 0개수={

    b_i where 그룹 i-1에서 k=0꼴(1로시작)일때

    b_i+1 where 그룹 i-1에서 k!=0꼴(01로 시작)일때

}이다.

 

즉 그룹 i까지 표현하는 경우의 수는 그룹i가 사용가능한 0의 개수에 의존하고, 이는 그룹 i-1의 표현에 의존한다. 의존성이 DAG형태이므로 DP가 가능하다. 최종적으로 아래와 같은 점화식을 세울 수 있다.

f(i,j)=그룹i를 (j=F이면 k=0(1로 시작), j=T이면 k!=0(01로 시작))형태로 할 때, 그룹 i까지 표현하는 가능한 경우의 수

f(i,j)={

    f(i-1,F)+f(i-1,T) where j=F

    f(i-1,F)*floor(b_i/2)+f(i-1,T)*floor((b_i+1)/2) where j=T

}

 

시간복잡도 분석)

상태개수 = 그룹개수 = O(logN) (피보나치수가 지수적으로 증가함)

상태당 계산량 = O(1)

그러므로 O(logN)

 

이 문제에 대한 논문

https://www.fq.math.ca/Scanned/37-1/bicknell.pdf
 

관련  문제

boj 3565