shjgkwo   1년 전

음, 이걸 뭐라고 설명해야하지

동일한 숫자내에서는 일단 큰것부터 연속적인것을 선택하는게 좋고 따라서, 연속적인 게 아니면 백트랙

그 무게를 더 이상 뺄 수 없거나, 그 무게가 없으면, 뺄 수 있는 다음 무게를 찾아서 빼주고

나머지는 연속적인 합에서 허용되는 범위라면, 무조건 그걸 가져가고 백트랙


대충 이런 내용인데요, 일반적인 경우라면 O(2^50) 으로 시간초과가 나야 정상이지만,

시간초과가 안나네요? 피보나치 성질때문에 그런것 같은데...

증명해주실 수 있는 수학깡패분 계신가요 ㅠㅠ?

baekjoon   1년 전

Zeckendorf Representation: http://mathworld.wolfram.com/ZeckendorfRepresentat...

아마 이것때문에 그렇지 않을까요?

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