static long long table[91][2]; //실수했던 부분
static int K;
static void table_init(void)
{
table[1][0] = 2;
table[1][1] = 1;
for (int i = 2; i <= 90; i++)
{
table[i][1] = table[i - 1][0];
table[i][0] = table[i - 1][0] + table[i - 1][1];
}
}최대공약수는 유클리드 호제법을 이용하여 구할 수 있고, 그 방식은 아래와 같다.
a > b; gcd(a, b) = gcd(b, a % b)
a > b = 0; gcd(a, 0) = a
이렇게 재귀적으로 구할 수 있다.
문제에서는 해당작업의 반복횟수가 주어졌을 때, 그 횟수를 만족하는 여러개의 두 수의 집합 중,
a가 제일 작고, 제일 작은 a가 여러개 일 경우 제일 작은 b가 되는 집합을 출력하는 것이다.
그래서 시작을 (a, 0) 으로 잡고 시작했다.
여기서 a == 1로 하고 거슬러 올라가면 된다.
(1, 0) -> (2, 1) 이 되어야 한다.
즉, 후자에 경우 a 자리에 오는 것은 (b * 2)가 되어야 한다. b * 1은 조건 상 될 수 없고,
b * 3 이상으로 가면 a가 제일 작아야 된다는 정답 조건을 만족하지 못한다.
이 이후 부터는 (a1, b1) -> (a2, b2) 를 만든다고 했을 때,
b2 = a1, a2 = a1 + b1이 되어야 한다. a1 * n (n > 1) 로 해도 상관은 없지만 조건을 만족하지 못한다.
이번에는 a == 2로 한뒤 거슬러 올라가되 되기는 하지만 역시 조건을 만족하지 못한다.
위 알고리즘이 table_init()에 동작방식이다.
정리하고 보니 제일 작은 b는 사실 신경 쓸 필요가 없는 조건 같다.
그리고 입력으로 주어지는 K가 최대 90까지 인데,
이렇게 누적해나가는 방식으로 int에서 오버플로우가 나는지 예상하지 못했다.
주의해야 할 만한 부분이다.
