[BAEKJOON] 2193번 이친수

이게 원래 짰던 코드이다

만약 3자리 수라면 100이고 111까지만 확인하면 된다 왜냐하면

000부터 011까지는 0이 맨 앞에 있기 때문에 어짜피 되지 않는다.

따라서 cache를 두고 x는 자릿 수 y는 decimal숫자로 해서

만약 2자리수의 decimal 3을 미리 구해놓았다면

되는지 되지 않는지를 판단하는 것이다.

하지만 문제가 있었다

이것이 범위는 90자리 즉 pow(2,90)인 것이다.

vector로 저 범위의 공간을 만들 수가 없다.

#include <iostream> #include <vector> #include <fstream> #include <algorithm> #include <string> using namespace std; vector<vector<int>> cache = vector<vector<int>>(91, vector<int>(pow(2, 20), -1)); string dec_to_bin(unsigned long long dec, int place) { string ret; int index = 0; while (place--) { ret.push_back((dec >> index) & 1); index++; } reverse(ret.begin(), ret.end()); return ret; } unsigned long long bin_to_dec(string bin) { unsigned long long ret = 0; int size = bin.size() - 1, index = 0; while (size >= 0) { ret += bin[index] * pow(2, size--); index++; } return ret; } int is_pinary_number(unsigned long long dec, string bin) { if (bin[0] == 0) { return 0; } int&ret = cache[bin.size()][dec]; if (ret != -1) { return ret; } int count = 0; while (bin[bin.size() - 1] != 0) { count++; bin.erase(bin.end() - 1); if (count >= 2) { return ret = 0; } if (bin.empty()) { return 1; } } bin.erase(bin.end() - 1); return ret = is_pinary_number(bin_to_dec(bin), bin); } int main() { unsigned long long result = 0; for (unsigned long long j = pow(2, k - 1); j < pow(2, k); j++) { if (is_pinary_number(j, dec_to_bin(j, k)) == 1) result++; } cout << result << endl; }

일단 vector로 만들 수 있는 모든 범위까지 출력을 해보았다.

1번째 : 1

2번째 : 1

3번째 : 2

4번째 : 3

5번째 : 5

6번째 : 8

7번째 : 13

8번째 : 21

9번째 : 34

10번째 : 55

11번째 : 89

12번째 : 144

13번째 : 233

14번째 : 377

15번째 : 610

16번째 : 987

(너무 느려서 중간에 끊었다)

이렇게 답이 나왔다 그런데 답을 보면 규칙이 있다.

바로 피보나치이다.

하...

사실 정답을 인터넷으로 검색한 이후에 피보나치 인것을 먼저 알고

그리고 저 코드를 돌려보았는데 피보나치가 나왔다.

이 코드가 내가 맨 먼저 인터넷에서 찾은 코드이다.

#include <iostream> #include <fstream> using namespace std; int main() { int input; cin >> input; unsigned long long answer = 1, index1 = 1, index2 = 1; for (int j = 2; j < input; j++) { answer = index1 + index2; index1 = index2; index2 = answer; } cout << answer << endl; }

그리고 피보나치를 연습하기 위해 dp로 피보나치를 구현해본 코드이다.

#include <iostream> #include <fstream> #include <vector> using namespace std; vector<unsigned long long> cache = vector<unsigned long long>(91, -1); unsigned long long fibo(unsigned long long n) { if (n == 1) return 1; if (n == 2) return 1; unsigned long long& ret = cache[n]; if (ret != -1) return ret; return ret = fibo(n - 1) + fibo(n - 2); } int main() { int input; cin >> input; cout << fibo(input) << endl; }

1번째 : 1

2번째 : 1

3번째 : 2

4번째 : 3

5번째 : 5

6번째 : 8

7번째 : 13

8번째 : 21

9번째 : 34

10번째 : 55

11번째 : 89

12번째 : 144

13번째 : 233

14번째 : 377

15번째 : 610

16번째 : 987

17번째 : 1597

18번째 : 2584

19번째 : 4181

20번째 : 6765

21번째 : 10946

22번째 : 17711

23번째 : 28657

24번째 : 46368

25번째 : 75025

26번째 : 121393

27번째 : 196418

28번째 : 317811

29번째 : 514229

30번째 : 832040

31번째 : 1346269

32번째 : 2178309

33번째 : 3524578

34번째 : 5702887

35번째 : 9227465

36번째 : 14930352

37번째 : 24157817

38번째 : 39088169

39번째 : 63245986

40번째 : 102334155

41번째 : 165580141

42번째 : 267914296

43번째 : 433494437

44번째 : 701408733

45번째 : 1134903170

46번째 : 1836311903

47번째 : 2971215073

48번째 : 4807526976

49번째 : 7778742049

50번째 : 12586269025

51번째 : 20365011074

52번째 : 32951280099

53번째 : 53316291173

54번째 : 86267571272

55번째 : 139583862445

56번째 : 225851433717

57번째 : 365435296162

58번째 : 591286729879

59번째 : 956722026041

60번째 : 1548008755920

61번째 : 2504730781961

62번째 : 4052739537881

63번째 : 6557470319842

64번째 : 10610209857723

65번째 : 17167680177565

66번째 : 27777890035288

67번째 : 44945570212853

68번째 : 72723460248141

69번째 : 117669030460994

70번째 : 190392490709135

71번째 : 308061521170129

72번째 : 498454011879264

73번째 : 806515533049393

74번째 : 1304969544928657

75번째 : 2111485077978050

76번째 : 3416454622906707

77번째 : 5527939700884757

78번째 : 8944394323791464

79번째 : 14472334024676221

80번째 : 23416728348467685

81번째 : 37889062373143906

82번째 : 61305790721611591

83번째 : 99194853094755497

84번째 : 160500643816367088

85번째 : 259695496911122585

86번째 : 420196140727489673

87번째 : 679891637638612258

88번째 : 1100087778366101931

89번째 : 1779979416004714189

90번째 : 2880067194370816120

그리고 항상 범위를 조심하자

나는 항상 범위에서 문제가 난다 8_8