백준 33489: 수열의 점수
https://www.acmicpc.net/problem/33489
x<X, y<Y인 x와 y중에서 수열의 점수가 가장 높은 것을 찾는 문제다.
A_i 를 x와 y에 대해 표현하면... 직접 써보자.
A_0 = x
A_1 = y
A_2 = x - y
A_3 = -x + 2y
A_4 = 2x - 3y
A_5 = -3x + 5y
A_6 = 5x - 8y
.....
규칙이 보이는지? x와 y의 계수는 피보나치 수열의 숫자들이다.
x/y=R이라고 두자.
그럼 A_i>0일때마다 1점을 얻으니,
0점: x>0 (당연한 소리)
1점: y>0 (당연한 소리)
x와 y 값에 상관없이 1점은 기본으로 받을 수 있다. 계속해보겠다.
2점: R>1/1
3점: R<2/1
4점: R>3/2
5점: R<5/3
6점: R>8/5
7점: R<13/8
8점: R>21/13
.....
역시나 규칙이 보인다.
R값은 홀수번째 연속된 두 피보나치 수의 비율보다 작아야 하고 짝수번째 연속된 두 피보나치 수의 비율보다 커야 한다.
결과적으로 말하자면 x와 y를 고르려면 주어진 범위 내에서 고를 수 있는 가장 큰 연속된 두 피보나치 수를 고르면 된다.
왜 그럴까?
p1, p2가 연속된 두 피보나치 수라고 해보자. (ex: p1=8, p2=13)
R<p2/p1이어야 7점을 얻을 수 있다.
자 이때, R=p2/p1이라면, 6점까지의 점수는 받을 수 있다는 게 보장된다.
연속된 두 피보나치의 비율은 특정 수로 수렴한다는 것이 알려져 있다. (이 문제에선 중요하지 않지만, 황금비인 1.618.... 으로 수렴한다 그래서 나는 이게 황금비에 가장 가까운 숫자를 제시하는 문제인가 고민했었다.)
이런 식으로 값이 황금비인 1.618...보다 큰 값과 작은 값을 번갈아가면서 점점 가까워진다.
저 그래프에서 x가 짝수일 때는 y값이 R값의 upper bound이고, x가 홀수일 때는 y값이 R값의 lower bound이다.
파란색으로 칠한 범위의 y값 안에 R값이 들어가야 하는 것이다.
만약 R=p2/p1이면 그 전의 피보나치 비율들에 의한 범위 안에는 들어간다는 게 보장된다.
R=p2/p1이면 R<p2/p1은 거짓이다.
따라서 7점은 얻을 수 없다.
그렇다면 p2/p1보다 작은 R을 만드는 x, y값을 찾아볼까?
다만 6점을 얻는 조건 중에 R>8/5라는 조건이 있으므로
R이 13/8보다 작으면서도 8/5보다는 크게 하는 게 중요하다.
그냥 13/8보다 작으면서 제일 큰 R을 찾아보자.
그러면 y는 그대로 8로 두는 게 좋다. 분모가 가장 커야 R값의 변화가 가장 작을 테니 말이다.
그럼 x는 13보다 1 작은 12로 두어야 한다.
이러면 12/8인데, 이는 8/5보다 작다. 이럴 수가!
p2, p1를 다루게 두어도 결과가 똑같이 나온다.
증명은 귀찮아서 안했지만 아마 그럴 것이다. (원래 코딩문제 풀때는 이러는게 맞긴함)
하지만 결국에는 주어진 범위 내에서 가장 큰 연속된 피보나치 수 2개를 x와 y로 설정하면 된다.
ex: X=100, Y=100 => x=89, y=55
X=88, Y=100 => x=55, y=34
X=100, Y=50 => x=55, y=34
X=10000, Y=30 => x=34, y=21