14856 조금 똑똑한 뢰벗과 조금 잘생긴 사냐 (백준, python3)

 

시간 제한	메모리 제한
1초	128MB

문제

*이 문제는 실제 인물과는 관련이 없습니다.*

옛날 먼 옛날, 사냐라는 사람이 살았습니다. 사냐라는 사람은 뢰벗이라는 친구가 있었는데, 둘은 매우 닮았지만, 뢰벗이 좀 더 똑똑하고, 사냐가 좀 더 잘생겼다고 합니다. 뢰벗은 오보워치(Ovorwatch) 라는 게임에서 500점으로 상위 100.00%였습니다. 사냐는 이러한 뢰벗을 놀리기를 좋아했습니다. 이에 열을 받은 뢰벗은, 사냐에게 자신이 오보워치 500점을 탈출한다면, 자신이 내는 문제를 평생 풀도록 하겠다는 내기를 했고, 사냐는 뢰벗이 설마 탈출하겠냐는 생각으로 수락했습니다.

그런데 그 일이 벌어졌습니다.

뢰벗은 오보워치 점수를 무려 600점대 까지 올렸고, 사냐는 내기 때문에 뢰벗이 내는 문제를 평생 풀어야 하게 되었습니다. 뢰벗은 사냐에게 자신이 주는 자연수를 연속하지 않은 피보나치 수들의 합으로 나타내게 시켰습니다. (피보나치 수열이란 F(1) = 1, F(2) = 2, F(n+2) = F(n+1) + F(n)으로 정의되는 수열입니다.) 멍청한 사냐는 피보나치 수열을 손으로 계산하는데, 시간이 너무 오래걸려 미칠것만 같아졌습니다. 이에 똑똑한 뢰벗은 그것도 계산 못하냐며 놀렸고, 사냐는 시무룩해졌습니다. 시무룩해진 사냐의 노동을 도와줄 프로그램을 짜봅시다.

 

입력

자연수 N을 입력받는다. (N < 1e18)

 

출력

자연수 N이 연속되지 않은 i1 < i2 < ... < ik에 대하여 F(i1) + F(i2) + ... + F(ik)로 나타내어 진다면, 첫째 줄에 k를 출력하고, 둘째 줄에 F(i1), F(i2), ... , F(ik)를 사이에 공백을 두고 출력하여라. 아니라면, 첫째 줄에 -1을 출력하여라. 만일 여러 가지 방법으로 연속하지 않은 피보나치 수들의 합으로 나타낼 수 있다면, 그 가운데 항의 수가 가장 많은 것을 출력하여라.

 

---

풀이

1e18까지의 피보나치 수를 구해보면 항이 87개 뿐이므로 재귀를 돌려도 충분히 구할 수 있다. 하지만 피보나치 수열에는 재밌는 성질이 하나 있다. 1, 2로 시작하는 피보나치 수를 쭉 나열해보자.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946...

이 숫자들이 딱 하나씩만 있다고 해보고 적절히 골라 합해서 여러 자연수들을 만들어보자.

	1	2	3	5	8	13	21	...	1, 0으로 표현
1	V								1
2		V							10
3			V						100
4	V		V						101
5				V					1000
6	V			V					1001
7		V		V					1010
8					V				10000
9	V				V				10001
10		V			V				10010
11			V		V				10100
12	V		V		V				10101
13						V			100000
14	V					V			100001
15		V				V			100010
16			V			V			100100
17	V		V			V			100101
18				V		V			101000
19	V			V		V			101001
20		V		V		V			101010
21							V		1000000
22	V						V		1000001
23		V					V		1000010
24			V				V		1000100
25	V		V				V		1000101
26				V			V		1001000
27	V			V			V		1001001
28		V		V			V		1001010
29					V		V		1010000
30	V				V		V		1010001
...									...

사실 10까지 해보면 대충 규칙이 존재함을 알아차릴 수 있다. 6은 피보나치 수 5와 1의 합으로 표현이 가능하다. 7은 5와 2로, 8은 5와 3으로 표현할 수 있으나 8 자체가 피보나치수이므로 8로 표현할 수 있다.

 

규칙을 정리해보면,

1. 어떤 수 k를 연속하지 않은 서로 다른 피보나치 수들 F의 합으로 표현 가능하다고 해보자.
2. k+1은 F의 가장 작은 피보나치 수를 다음 단계의 피보나치 수로 바꾸는 것으로 표현할 수 있다.
3. 만약 F의 가장 작은 피보나치 수를 다음 단계의 피보나치 수로 바꿀 때 피보나치 수가 연속하게 되면, 가장 작은 피보나치 수를 삭제하고 2를 다시 실행한다.

이게 되는 이유는 뭘까?

 

어떤 수 k가 있다. 이 수보다 크지 않은 가장 큰 피보나치 수를 a라고 하자. k = a + k' 이다. k' 이 0 이상이라면 k' 보다 크지 않은 가장 큰 피보나치 수를 b라고 하자. k = a + b + k'' 이다. k''이 0 이상이라면 k'' 보다 크지 않은 가장 큰 피보나치 수를 c라고 하자. k = a + b + c + k''' 이다. 이 과정을 반복하면 가장 작은 피보나치 수는 1이므로 1보다 작은 자연수가 존재할 수 없어 어떤 자연수 k라도 적절한 피보나치 수의 조합으로 표현할 수 있는 것이 된다.

 

그렇다면 왜 위의 표에는 연속한 피보나치 수의 합은 등장하지 않는 것일까? 사실은 등장할 수도 있다. 문제의 조건을 무시해보면 8 = 5 + 3으로 연속한 두 개의 피보나치 수의 합으로 표현된다. 당연히 F[i] = F[i - 1] + F[i - 2] 이기 때문이다. 그런데 여기서 중요한 것은 "이 수보다 크지 않은 가장 큰 피보나치 수"를 선택한다는 것이다. 만약 "이 수보다 작은 가장 큰 피보나치 수"를 선택했다면 8 = 5 + 3 꼴로 표현된다. 그런데 어떤 수 k가 피보나치 수일 경우, 피보나치 수를 곧바로 선택하게된다는 것이다. 이럴 경우 남는 항은 0이며 더 이상 선택할 피보나치 수는 없다. 연속하는 피보나치 수를 선택하게 되는 경우는 k보다 작으면서 가장 큰 두 개의 피보나치 수를 선택하는 것 외에는 없다. 따라서 문제의 조건에 맞게 연속하는 피보나치 수의 선택 없이 유일한 방법으로 피보나치 수를 선택해 모든 자연수를 표현하는 것이 가능하다.

 

증명이 굉장히 어설프지만 (사실 증명이라고 하기 어려움) 제켄도르프 분해(또는 정리, 표현)로 알려진 개념이다.

https://mathstorehouse.com/archives/mathematics/algebra/arithmetic/5943/

피보나치 수열(Fibonacci sequence)을 이용한 자연수의 분할 - Math Storehouse

제켄도르프 분해의 과정을 그대로 구현해주면 매우 쉽게 골드 4를 먹을 수 있는 문제.

 

 

정답 코드

import sys
from collections import deque
input = sys.stdin.readline
def solution():
    fib = deque([1, 2])
    N = int(input())
    while fib[-1] + fib[-2] <= N:
        fib.append(fib[-1] + fib[-2])
    result = []
    while fib:
        if fib[-1] <= N:
            result.append(fib.pop())
            N -= result[-1]
        else:
            fib.pop()
    print(len(result))
    result.reverse()
    print(*result)
solution()