백준 9009번: 피보나치

자연수 n이 주어질 때, n을 서로 다른 피보나치 수의 합으로 나타내는 문제이다.

이 때 사용하는 피보나치 수의 갯수는 최소가 되어야 한다.

 

풀이는 생각보다 간단하다. n보다 같거나 작은 피보나치 수 중 가장 큰 피보나치 수를 사용하고, 이를 반복하면 된다. 가령 n=100이면 89를 사용하고, 남은 11에 대해서 8을 사용하고, 또 남은 3에 대해 3을 사용하면 된다.

답을 때려맞추기는 상당히 쉬운 문제이지만, 왜 그게 성립하는지 증명하기는 상당히 까다롭다.

과연 이 방법이 왜 최적의 해를 가져올까?

 

예시와 함께 증명을 해보자.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

 

89~143까지의 숫자에 대해 생각을 해보자.

 

i) 임의의 수에 대해, n보다 같거나 작은 피보나치 수 중 가장 큰 것, 두번째로 큰 것 중 단 하나만 사용하게 된다. 위 예시에서는 55, 89 중 단 하나만 사용해야 한다.

i-1) 만약 둘 다 사용하지 않을 경우, 그 아래 모든 수들의 합이 만드려는 수보다 작으므로 불가능하다. 위 예시에서는 1~34까지 더한 것이 89보다 작으므로 불가능하다.

i-2) 둘 다 사용할 경우 만드려는 숫자보다 커지므로 불가능하다. 위 예시에서는 55 + 89 = 144 > 143이므로 불가능하다.

 

ii) n보다 같거나 작은 피보나치 수 중 두번째로 큰 것을 사용하면, 최적의 해를 만들어낼 수 없다.

위 예시에서 89 대신 55를 사용했다고 가정해보자. 이 때 만들 수 있는 최댓값은 얼마일까?

만약 34를 사용한다면, 34과 55 두 개를 89로 바꿀 수 있으므로 최소 갯수가 아니다. 따라서 34는 사용할 수 없다. 21을 사용하면, 13은 사용할 수 없다. 13과 21 두 개를 34로 바꿀 수 있기 때문이다.

간단히 말해 연속하는 두 피보나치 수를 사용하면 최적이 되지 않는다. 따라서 최적 조건을 만족하며 만들 수 있는 최댓값은 두 칸씩 건너뛰는, 55 + 21 + 8 + 3 + 1이다. 이 값을 t라고 하자. t는 얼마일까?

t에 1을 더해보자.

 

55 + 21 + 8 + 3 + 1 + 1

= 55 + 21 + 8 + 3 + 2

= 55 + 21 + 8 + 5

= 55 + 21 + 13

= 55 + 34

= 89

 

숫자가 서로 상쇄되며 89가 되는 것을 확인할 수 있다. 즉, t + 1 = 89에서 t < 89이므로 우리가 원하는 숫자를 만들어낼 수 없다.

 

i), ii)에 의해 최적의 해를 만드려면, 항상 n보다 같거나 작은 피보나치 수 중 가장 큰 것을 사용해야 한다.

 

 

코드는 아래와 같다.

9009.cpp