# [Gold I] 수열의 점수 [문제 링크](https://www.acmicpc.net/problem/33489) ## 문제 설명 <p>두 정수 $x$와 $y$가 주어질 때, 무한한 길이의 정수 수열 $A$를 아래와 같이 정의한다.</p> <ul> <li>$A_1 = x$</li> <li>$A_2 = y$</li> <li>$A_{k} = A_{k-2} - A_{k-1}(k \geq 3)$</li> </ul> <p>당신은 $1 \leq x \leq X;$ $1 \leq y \leq Y$를 만족하는 정수 $x$, $y$를 선택할 수 있다.</p> <p>수열에서 $0$ 이하의 수가 $k$번째 항에서 처음 등장하였을 때, $k$를 수열 $A$의 점수라고 한다. $x$, $y$를 어떻게 정하더라도 상관없이 수열에 $0$ 이하의 수가 적어도 한 번 등장함을 증명할 수 있다. 수열 $A$의 점수를 최대화하는 $x$, $y$를 찾아보자.</p> ## 입력 <p>첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 아래와 같이 주어진다.</p> <p>각 테스트 케이스는 한 줄로 이루어져 있고, 두 개의 정수 $X$, $Y$가 공백으로 구분되어 주어진다.</p> ## 출력 <p>각 테스트 케이스에 대해, 수열 $A$의 점수를 최대화하는 $x$와 $y$를 공백으로 구분하여 출력한다.</p> <p>정답이 여러 개 존재한다면 그중 아무거나 출력해도 상관없다.</p> ## 풀이 #### 1 1 부터 시작해서 역추적으로 답을 찾으면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int x, y; cin >> x >> y; int lastX = 1, lastY = 1; while(true) { int nextX = lastX+lastY; int nextY = lastX; if(nextX>x || nextY>y) break; lastX = nextX; lastY = nextY; } cout << lastX << ' ' << lastY << '\n'; } } ```