https://www.acmicpc.net/problem/33489
문제 요약
- 무한한 길이의 수열 A를 정의함 : x,y로 시작하고 (앞항 - 뒤항) 을 계속 반복
- 수열에서 최초로 0이하가 등장할때까지의 길이를 최대로 하는 x,y를 선택
- 1<=x<=X, 1<=y<=Y (3*10^5)
접근법(실패)
- 수식을 전개하면
- x > 0
- y > 0
- x-y > 0
- 2y-x > 0
- 2x-3y > 0
- ....
- 부등호가 나오고, 기울기가(셋째항부터) 1, 1/2, 2/3, 3/5, 5/8, ..... 피보나치를 이용한 기울기가 나옴
- 두 직선 사이의 영역의 숫자들일텐데, 직선을 최대한 촘촘히 했을때 얻을 수 있는 정수 쌍을 구하자로 접근했음
- x가 가장 클때 유리할 것이라고 판단했는데 실패함
실패이유 찾기
- 적당히 작은 값에 대해서 완전탐색으로 찾아봄
- (X,Y)의 모든 경우에 대해서 수열을 전개해서 가장 큰 값이 나오는 경우를 찾는 방식으로 완전 탐색
- 그런데 수열을 전개하다가 보니 역피보나치라는 것을 깨달음
- 값이 줄어드는 것처럼 보이는데 반대로 하면 피보나치 수열임
접근법(성공)
- 어떤 숫자로 시작하든 마지막에는 (1,1), (1,2), (2,1) 중 하나로 끝남
- (0,x) 는 당연히 아니고
- (3,2) 는 (2,1)의 여지가 있음
- 반대로 (1,1), (1,2), (2,1)로 시작해서 (Y,X)를 만족하는 가장 긴 수열을 찾아봄
- 왜 (Y,X)이냐면, 피보나치의 역으로 전개했을때가 문제에서 주어진 수열이기때문임
- 피보나치가 빨리 커지기때문에 3*10^5까지 만드는데 수행횟수가 크지 않음 => 탐색 가능
왜 실패했을까
- 아무래도 정수를 찾아야하기 때문에 오히려 중간 어딘가가 영역에 잘 맞을수도 있는 것 같다.
newbieski