문제
https://www.acmicpc.net/problem/2502
문제해설
이 문제는 피보나치 수열을 응용한 문제이다.
며칠이 지났는지와 준 떡의 갯수가 주어지면 첫날과 두번째 날에 준 떡의 갯수를 맞추면 된다.
문제풀이
첫날에 준 떡을 a개, 둘째날에 준 떡을 b개라고 하면
1일 : a
2일 : b
3일 : a + b
4일 : a + 2b
5일 : 2a + 3b
6일 : 3a + 5b
이런식으로 증가하게 된다.
문제의 조건에서 총 30일까지 있기 때문에 30일까지 저 식을 다 만들어놓고
a와 b에 들어갈 수를 완탐으로 확인해보면 된다.
예를들어 6번째 날에 41개를 주었다면
3a + 5b = 41라는 식을 도출할 수 있고
이중포문으로 1부터 10000까지 돌며 a와 b에 대입하며 맞는수를 찾았다.
만까지만 도는 이유는 만까지만해도 충분히 수가 커지기 때문이다. 사실 100까지만 해도 될듯..
전체코드
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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int arr[31][2];
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cin.tie(NULL);
int d, k;
cin >> d >> k;
arr[1][0] = 1;
arr[2][1] = 1;
for (int i = 3; i < 31; i++) {
arr[i][0] = arr[i - 2][0] + arr[i - 1][0];
arr[i][1] = arr[i - 2][1] + arr[i - 1][1];
}
for (int i = 1; i < 10000; i++) {
for (int j = 1; j < 10000; j++) {
if (i * arr[d][0] + j * arr[d][1] == k) {
cout << i << "\n" << j;
return 0;
}
if (i * arr[d][0] + j * arr[d][1] > k)
break;
}
}
return 0;
}