백준 2502 - 떡 먹는 호랑이 (C++)
피보나치 수열을 응용한 문제이다.
D일차에 호랑이를 만났다면, 호랑이는 반드시 D-1일차에 받은 떡과 D-2일차에 받은 떡을 합친 만큼 받아야 물러선다.
이 때, D일차에 떡을 K개 줬다면 첫 날과 둘째 날은 몇 개의 떡을 줬을지 구하는 문제이다.
문제 풀이
먼저, 점화식을 세워보자.
N일차에 호랑이에게 준 떡의 개수는 N-1일차에 준 떡의 개수 + N-2일차에 준 떡의 개수이다.
//R(N)을 N일차에 준 떡의 개수라고 한다면.
R(N) = R(N - 1) + R(N - 2)
이 식을 이번엔 첫째항부터 계산해보자.
첫날에 준 떡의 개수를 a라고 하고, 둘째날에 준 떡의 개수를 b라고 한다면.
1일차 : a
2일차 : b
3일차 : a + b
4일차 : a + 2b
5일차 : 2a + 3b
6일차 : 3a + 5b
7일차 : 5a + 8b이런 식으로 식을 세워볼 수 있다.
눈치챘을 수도 있지만, a와 b의 계수는 피보나치 수열을 이루고 있다.
피보나치 수열의 항을 보면 (1, 1, 2, 3, 5, 8, 13, 21.....) 이다.
피보나치 수열의 n번째 항을 Fibo(n)이라고 한다면
1일차 : a
2일차 : b
3일차 : Fibo(1) * a + Fibo(2) * b
4일차 : Fibo(2) * a + Fibo(3) * b
5일차 : Fibo(3) * a + Fibo(4) * b
6일차 : Fibo(4) * a + Fibo(5) * b
7일차 : Fibo(5) * a + Fibo(6) * b
이렇게 표현해볼 수 있다.
이를 다시 점화식으로 바꿔보면
//D(N)은 N일차에 준 떡의 개수, a는 첫날에 준 떡의 개수, b는 둘째날에 준 떡의 개수
D(N) = Fibo(N - 2) * a + Fibo(N - 1) * b이렇게 세워볼 수 있다.
이제 반복문을 돌며 a와 b를 하나하나 대입해보며 나온 값이 입력받은 K와 같아진다면 a,b를 출력하면 된다.
하지만, 미지수가 두개인 문제를 해결하기 위해 2중 반복문을 돌게 되면 시간초과가 뜰 것이다.
즉, 위의 점화식을 기반으로 반복문을 한 번만 돌 수 있는 방법을 고안해야 한다.
그럼 어떻게 해야 할까?
D(N) = Fibo(N - 2) * a + Fibo(N - 1) * b;
=> D(N) - Fibo(N - 1) * b = Fibo(N - 2) * a;
이렇게 식을 바꿔볼 수 있다.
이 식을 생각해보면 D(N) - Fibo(N-1) * b 는 반드시 Fibo(N - 2)의 배수가 된다.
바꿔 말하면, D(N) - Fibo(N-1) * b 를 Fibo(N - 2)로 나눈 나머지가 0이라면, 위 식을 만족하는 정수 a,b쌍이 있다고 생각할 수 있다.
이 때, D(N) - Fibo(N-1) * b 를 Fibo(N -2)로 나눈 값이 a가 될 것이다.
a를 구했다면, 식에 대입해 이어서 b를 구할 수 있다.
a,b 쌍을 구했고, 1 <= a <= b 를 만족한다면, 그대로 a,b를 출력하면 끝이다.
풀이 코드
std::vector<int> Fibonacci;
int Days = 0;
int LastRiceCakes = 0;
std::cin >> Days >> LastRiceCakes;
Fibonacci.resize(Days + 1);
필요한 변수를 선언하고, 값을 입력받았다.
이후, 피보나치 수열을 저장하기 위한 배열을 resize해주었다.
void DoFibonacci()
{
Fibonacci[1] = 1;
Fibonacci[2] = 1;
for (int i = 3; i <= Days; i++)
{
Fibonacci[i] = Fibonacci[i- 1] + Fibonacci[i- 2];
}
}이후, 이렇게 피보나치 수열을 구하는 함수를 만들어서 피보나치 수열의 배열을 채워주자.
for (int SecondRiceCakes = 1; SecondRiceCakes <= 100000; SecondRiceCakes++)
{
int FirstRiceCakes = 0;
if ((LastRiceCakes - Fibonacci[Days - 1] * SecondRiceCakes) % Fibonacci[Days - 2] == 0)
{
FirstRiceCakes = (LastRiceCakes - Fibonacci[Days - 1] * SecondRiceCakes) / Fibonacci[Days - 2];
if (FirstRiceCakes <= SecondRiceCakes)
{
std::cout << FirstRiceCakes << "\n" << SecondRiceCakes;
return 0;
}
}
}
다음은 이렇게 반복문을 돌며 조건을 체크하면 끝이다.
먼저, LastRiceCakes - Fibonacci[Days - 1] * i 가 Fibonacci[Days - 2]의 배수인지 체크해준다.
배수가 맞다면 나누기연산을 이용해 FirstRiceCakes 를 구해준다.
FirstRiceCakes <= SecondRiceCakes 를 만족한다면 그대로 두 숫자를 출력해주면 된다.
문제 자체가 어렵다기보단, 두개의 미지수를 구하기 위해 반복문을 한 번만 돌리는 아이디어를 구현하는 것이 다소 까다로운 문제였다. 아무래도 DP문제는 알고리즘보단 이런 사고력을 요하는 경우가 꽤 있기 때문에 여러 번 풀어보며 머리를 풀어두자.