백준 2502번 떡먹는 호랑이 C++ 구현해보기

---

```

백준 2502번 떡 먹는 호랑이 C++ 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 2502번 풀이

---

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

2502번: 떡 먹는 호랑이

 

 

 

백준 2502번 떡 먹는 호랑이는 

난이도 실버 등급의 문제로서

 

첫날 A

둘째날 B개의 떡을 호랑이에게 주고

3번째 날 그전에 날 + 그 전전날의 개수의 떡 (A+B)을 추가로 호랑이한테 주고

4번째 날 그전에 날 + 그 전전날의 개수의 떡 (A+2B)을 추가로 호랑이한테 주고

5번째 날 그전에 날 + 그 전전날의 개수의 떡 (2A+3B)을 추가로 호랑이한테 주는 경우

 

날짜의 수를 D (3이상 30 이하)

준 떡의 총 수를 K라고 할 때

 

D와 K가 주어질 때

A와 B를 구하는 문제이다

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

예를 들어 7과 218이 입력으로 주어질 때

 

답이 나오는 경우

A B가 아래와 같이

2
26

 

1일 차 : 2

2일 차 : 26

3일 차 : 2 26

4일 차 : 26 28

5일 차 : 28 54

6일 차 : 54 82

7일 차 : 82 136

8일 차 : 136 218

9일 차 : 218 354

 

10
21

 

10 21

21 31

31 52

52 83

83 135

135 218

218 353

 

18
16

 

18 16

16 34

34 50

50 84

84 134

134 218

218 352

26
11

 

26 11

11 37

37 48

48 85

85 133

133 218

218 351

34
6

 

34 6

6 40

40 46

46 86

86 132

132 218

218 350

42
1

 

42 1

1 43

43 44

44 87

87 131

131 218

218 349

 

등과 같이 매우 다양한 경우가 있습니다.

 

답을 구하는 방법은 많겠지만

 

저는 피보나치수열을 사용하였습니다.

 

A와 B 가 합 내에서

피보나치수열을 이룬다는 패턴을 알았기 때문입니다.

 

1 일차 A

2 일차 B

3 일차 A + B

4 일차 A + 2B

5 일차 2A + 3B

6 일차 3A + 5B

 

따라서 N일차 숫자는

피보나치수열(N-2)  * A + 피보나치 수열(N-1)  * B이고

 

피보나치 수열 값만 31일 차 까지 미리 구해준다음

A B 값을 주어진 값 K에 적용해보면

쉽게 풀렸습니다.

 

 

 

 

전체 코드는 다음과 같습니다

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <regex>
#include <unordered_map>

using namespace std;


int main()
{
	// 입력 최적화 
	std::cin.tie(NULL); 
	std::ios::sync_with_stdio(false);
	std::string inputStr;
	std::getline(std::cin, inputStr);
	std::stringstream ss(inputStr);

	int32_t days;
	ss >> days;

	int32_t riceCakeNum;
	ss >> riceCakeNum;

	const int32_t kMaxDays = 31;
	static std::array<int64_t, kMaxDays> fibArr;
	fibArr[0] = 0;
	fibArr[1] = 1;

	for (int i = 2; i < kMaxDays; i++)
	{
		fibArr[i] = (fibArr[i - 1] + fibArr[i - 2]);
	}

	int32_t mulA = fibArr[days - 2];
	int32_t mulB = fibArr[days - 1];

	for (int32_t A = 1; A <= riceCakeNum / mulA; A++)
	{
		int32_t tempAmul = mulA * A;
		for (int32_t B = 1; B <= riceCakeNum / mulA; B++)
		{
			int32_t tempBmul = mulB * B;
			if ((tempAmul + tempBmul) == riceCakeNum)
			{
				std::cout << A << "\n" << B;
				return 0;
			}
		}
	}
}

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

 

https://codemasterkimc.tistory.com/50

300년차 개발자의 좋은 코드 5계명 (Clean Code)

 

---