백준 2502번: 떡 먹는 호랑이 (C++)

https://www.acmicpc.net/problem/2502

2502번: 떡 먹는 호랑이

 

풀이

피보나치의 첫번째 항과 두번째 항을 구하는 문제.

먼저, 첫번째 항과 두번째 항만 구하면 되기 때문에 변수를 최대한 줄여 나타냈다.

 

 

그리고 첫번째 항과 두번째 항의 상수의 점화식을 도출해서 X[31][2]를 선언, 2차원 배열에 순서대로 저장해주었다.

(여기서는 2번째부터 표현했는데 다시보니 첫번째부터 구해도 됐다.) (X1 제일 앞에 1, X2 제일 앞에 0)

 

 

변수가 두개가 되기 때문에 정답이 여러개 나온다. 

그래서 두번째 항을 2부터 순서대로 대입해보고 첫번째 항인 A가 정수이고 B보다 작은 결과를 출력해주었다.

 

엄청 야매로 푼 것 같았는데 거의 비슷하게 푼 사람이 있어서 제대로 푼게 맞는지 의아심이 조금 든다.

 

전체 코드

#include <iostream>

using namespace std;

int main() {
	int D, K;
	int x[31][2] = { 0, };
	x[3][0] = 1;
	x[3][1] = 1;
	x[4][0] = 1;
	x[4][1] = 2;

	cin >> D >> K;

	for (int i = 5; i <= D; i++) {
		x[i][0] = x[i - 1][0] + x[i - 2][0];
		x[i][1] = x[i - 1][1] + x[i - 2][1];
	}

	for (int i = 2; i < K; i++) {
		double A = (double)(K - x[D][1] * i) / (double)x[D][0];
		if (!(A - (int)A) && A <= i) {
			cout << (int)A << '\n' << i;
			return 0;
		}
	}
}