실력키우기 떡 먹는 호랑이(C++)

1997 : 떡 먹는 호랑이

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 895 회    시도횟수: 1650 회    Special Judge

하루에 한 번 산을 넘어가는 떡 장사 할머니는 호랑이에게 떡을 주어야 산을 넘어갈 수 있는데, 욕심 많은 호랑이는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야만 할머니를 무사히 보내 준다고 한다.

 

예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다.

 

우리는 산을 무사히 넘어온 할머니에게 오늘 호랑이에게 몇 개의 떡을 주었는지, 그리고 오늘이 호랑이를 만나 떡을 준지 며칠이 되었는지를 알아내었다. 할머니가 호랑이를 만나서 무사히 넘어온 D째 날에 준 떡의 개수가 K개임을 알 때, 여러분은 할머니가 호랑이를 처음 만난 날에 준 떡의 개수 A, 그리고 그 다음 날에 호랑이에게 준 떡의 개수 B를 계산하는 프로그램을 작성하시오. 이 문제에서는 항상 1≤A≤B 이다.

 

예를 들어 여섯 번째 날에 산을 무사히 넘어온 할머니가 호랑이에게 준 떡이 모두 41개라면, 호랑이를 만난 첫 날에 준 떡의 수는 2개, 둘째 날에 준 떡의 수는 7개이다. 즉 셋째 날에는 9개, 넷째 날에는 16개, 다섯째 날에는 25개, 여섯째 날에는 41개이다. 따라서 A=2, B=7 이 된다. 단 어떤 경우에는 답이 되는 A, B가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 구해서 출력하면 된다.

 

첫째 줄에는 할머니가 넘어온 날 D (3≤D≤30)와 그 날 호랑이에게 준 떡의 개수 K (10≤K≤100,000)가 하나의 빈칸을 사이에 두고 주어진다.

첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤A≤B)가 존재한다.

[Copy] 6 41

[Copy] 2 7

[Copy] 7 218

[Copy] 10 21

출처 : KOI 본선 2008 초2

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

/**************************************************************     Problem: 1997     User: a132034     Language: C++     Result: Success     Time:1 ms     Memory:1740 kb ****************************************************************/     #include    <iostream> using namespace std;   int main() {     int D, K;     int * arr;     int * A;     int * B;     cin >> D >> K;       arr = new int[D];     arr[D - 1] = K;     A = new int[D];     B = new int[D];       A[0] = 1; A[1] = 0;     B[0] = 0; B[1] = 1;       for (int i = 2; i < D; ++i)     {         A[i] = A[i - 1] + A[i - 2];         B[i] = B[i - 1] + B[i - 2];     }       for (int i = 1; i <= K/2; ++i)     {         for (int j = i; j <= K; ++j)         {             if (K == (i*A[D - 1] + j*B[D - 1]))             {                 cout << i << endl << j << endl;                 return 0;             }             else if (K < (i*A[D - 1] + j*B[D - 1]))                 break;         }     }     //K = x*A[D-1] + y*B[D-1] 인 경우 x, y를 구하시오             return 0; }

차례대로 그냥 공책에 써 보았다. 

1일 : A

2일 : B

3일 : A+B

4일 : A+2B

5일 : 2A+3B

...

각각 배열로 표현해보기 위해 정리하면

A : 1 0 1 1 2 3 5 8 . . .

B : 0 1 1 2 3 5 8 13 . . .

보아하니 0번째와 1번째에만 각각 1 0 , 0 1을 넣어준 후에 입력받은 날짜 까지 1번째 전 값과 2번째 전 값을 더해주면서 만들어주면 

A의 계수와 B의 계수를 알 수 있고 

이 문제 자체는 2차 방정식을 푸는 것과 같으므로... 구한 값을 대입해보면 다음과 같다. 

Y = aX + bY ==>> K(해당일에 준 떡 갯수) = A(첫날 준 떡 갯수) * DA(계산해서 나온 당일 A의 계수) + B(둘째날 준 떡 갯수) * DB(계산해서 나온 당일 B의 계수)

이 식이 49번째 줄과 같다. 

우리는 입력받은 K를 알고, 입력받은 D를 이용해 DA, DB를 알 수 있으니 2차원 방정식을 푸는 것과 같다... 

하지만 구할 수 있는 식은 한개(두개일 수도... 우선 생각나는건 한개뿐이라..)

고민하다 보니 제약사항도 보이고.. 그냥 차례대로 수를 넣어가며 답을 찾아도 그리 오래걸리지 않을 것 같은 마음에 그대로 찾아보았다. 

떡의 갯수는 1<=A<=B이다. -> 그러므로 36번째 줄의 i(구하려는 A값)이 최대 K/2일 것이라고 생각했다. 

만약 입력값이 3 14일 경우 3일차에 14개를 줬다는 것이고 첫 날에 7개를 넘게 준다면 둘쨋날(B)에 7개보다 적게(A>B) 줄 것이고 제약사항에 어긋나기 때문이다. 

두번째로 45번째 줄에서 계산한 값이 K보다 큰 경우에는 바로 다음으로 넘어가게 break를 사용하였다. 필요없는 연산을 줄이기 위함. (사실 여기에서는 안 해도 통과는 할 정도)