[HackerRank] C++ Variadics

https://www.hackerrank.com/challenges/cpp-variadics/problem

C++ Variadics | HackerRank

Input & Output

 

첫 번째 Line :     testCase의 수

두 번째 Line :     x ( 찾을 숫자 )

세 번째 Line :     y ( 범위 계산에 사용될 값 )

 

범위 : 64 * y ~ 64 * y + 63

 

SamePle Input에서 "65 1" 의 경우, 65의 수를 64 * 1 ~ 64 * 1 + 63 사이, 즉 64 ~ 127 사이에서 찾아주는 것이다.

65는 64 바로 다음에 있으므로 두 번째 bit가 1로 바뀐다.

 

"10 0" 의 경우, 10의 수를 64 * 0 ~ 64 * 0 ~ 63 사이, 즉 0 ~ 63 사이에서 찾아주는 것이다.

10은 0으로부터 11칸 떨어져 있으므로 11번 째 bit가 1로 바뀐다.

 

 

Variadics template

 

Variadics template은 적어도 하나의 parameter Pack을 가지고 있는 template을 말한다.

(A template with at least one parameter pack is called a variadic template.)

 

parameter Pack이란 말 그대로 '매개변수 팩' 이다. 아래의 코드에서 ...에 해당한다.

template <typename First, typename ... Rest>

 

 

문제 풀이)

 

문제에서 반환형이 int인 reversed_binary_value<digits...>() 를 호출하고 있다. 우리는 이 함수를 구현하면 된다.

 

문제에서 digits로 넘어오는 bool형은 총 7개가 넘어온다. 범위는 항상 64개이므로, 2^6승이 넘어오는 것이다.

 

digits에서 0 0 0 0 0 0 0 은 0을 의미하고 1 0 0 0 0 0 0 은 1을, 0 1 0 0 0 0 0 은 2를 의미한다.

 

따라서 reversed_binary_value에서 parameter pack에서 bool형을 하나씩 빼내어 확인하면서 그 결과를 return

 

해주면 된다.

 

2^n으로 이루어지므로, int형 변수를 하나 받아야 하는데, reversed_binary_value 함수에서 int형까지 받는 것이

 

구현이 힘들고, 복잡해지기 때문에 ( 구현이 가능한 지도 잘 모르겠다 ... ) int형과 bool형의 parameter pack을 가진

 

calcBinary()라는 Variadics template을 하나 더 만들었다.

 

즉, reversed_binary_value에서 calcBinary에 0과 bool형의 parameter pack을 보내주면 calcBinary에서

 

결과 값을 리턴해주는 형태가 되는 것이다.

 

calcBinary의 재귀가 끝이 날 수 있도록 bool형의 parameter를 모두 쓴, 즉 calcBinary를 오버로딩하여

 

int형 하나만을 가진 함수이고 0만을 리턴하는 함수를 만들었다. 

 

< 소스 코드 >

#include <iostream>
using namespace std;

int Pow(int a, int b)
{
	int ret = 1;
	while (b > 0)
	{
		if (b % 2)
		{
			ret *= a;
		}
		a *= a;
		b /= 2;
	}
	return ret;
}

template<int n>
int calcBinary()
{
	return 0;
}

template <int n, bool first, bool ...rest>
int calcBinary()
{
	int ret = 0;
	if (first) ret = Pow(2, n);
	ret += calcBinary<n + 1, rest...>();
	return ret;
}

// Enter your code for reversed_binary_value<bool...>()
template <bool ...digits>
int reversed_binary_value()
{
	int ret = calcBinary<0, digits...>();
	return ret;
}

template <int n, bool...digits>
struct CheckValues {
	static void check(int x, int y)
	{
		CheckValues<n - 1, 0, digits...>::check(x, y);
		CheckValues<n - 1, 1, digits...>::check(x, y);
	}
};

template <bool...digits>
struct CheckValues<0, digits...> {
	static void check(int x, int y)
	{
		int z = reversed_binary_value<digits...>();
		std::cout << (z + 64 * y == x);
	}
};

int main()
{
	int t; std::cin >> t;

	for (int i = 0; i != t; ++i) {
		int x, y;
		cin >> x >> y;
		CheckValues<6>::check(x, y);
		cout << "\n";
	}
}