[백준] 2502 떡 먹는 호랑이 c++

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

2502번: 떡 먹는 호랑이

풀이

d-1번째 날에 호랑이에게 준 떡의 개수를 정하면 나머지날의 호랑이에게 준 떡의 개수가 정해지기 때문에 

d-1번째 떡의 수를 k/2+1부터 k까지 늘려가면서 가능한 경우를 출력했다.

떡의 개수가 음수가 되거나 n-1날 준 떡의 개수가 n번째보다 커지게 되면 안되기 때문에 return 했다.

#include<iostream>

using namespace std;

int d, k;//할머니가 넘어 온 날, 떡의 개수
//6 41


int a, b;
void mountain(int day, int riceCake1, int riceCake2)
{
	
	if (riceCake1 < 1 ||riceCake1>riceCake2 )
		return;

	if (day == d)
	{
		cout << riceCake1 << "\n" << riceCake2;
		exit(0);

	}
	
	
	
	mountain(day + 1,riceCake2-riceCake1, riceCake1);

}
int main()
{
	cin >> d >> k;
	for (int i = k / 2 + 1; i < k; i++)
	{
		
		mountain(2, i, k);
		
	}
}

다른 사람의 풀이

1  일         a 개

2  일         b개

3  일         a+b개

4  일         a+2b개

5일           2a+3b개

6일          3a+5b개

a에 붙는 계수는  1 0 1 1 2 3 5 ...  이를 배열에 담아서 A[4]=2로 표현

b에 붙는 계수는  0 1 1 2 3 5 ...          배열 A를 한칸씩 앞으로 당긴것과 비슷

k=A[d-1]*a +A[d]*b      b=(k-A[d-1]*a) /A[d]

a를 늘려가면서 아래 식이 만족하는 값을 찾으면 된다. (떡의 개수는 정수이기 때문에)

(k-A[d-1]*a) %A[d]==0

그리고 a의 값과  (k-A[d-1]*a) /A[d]을 출력해주면 된다.