[C++] 백준 2685번: 님비합

문제 링크

2685번: 님비합

문제 요약

각 테스트케이스마다 다음 사항을 구현해야 한다.
1. X, Y 두 수를 B진법으로 나타낸다.
2. B진법으로 나타낸 두 수를 각 자리끼리 더하고, 각 자리를 B로 나눈다.
3. 이 수를 10진법으로 바꾼다.

문제 요약

단순 구현 문제입니다. 10진수를 B진법으로 바꾸는 방법은 간단합니다.

1. 수를 B로 나눈 나머지를 별도로 저장하고, B로 나눈 몫으로 대체합니다.
2. 반복하다가 수가 B보다 작아지면 그 수도 저장합니다.

이렇게 순서대로 나온 나머지와 마지막 수를 역순으로 재배열하면 B진법 수가 됩니다. 어차피 연산에 사용할 것이기 때문에 굳이 역순으로 재배열하지는 않았습니다.

이제 두 수를 각 자리마다 더하고, B로 나눠줍니다. 그리고 이 수를 다시 10진수로 바꿔주면 됩니다.

10진수로 바꾸는 절차는, 자릿수가 N개이고, 각 자리의 수가 $A_i$일 때, $\sum\limits_{i = 1}^{N}A_i\times B^{i - 1}$을 해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

void func(vector<int>& v, int n, int b)
{
	while (1)
	{
		v.push_back(n % b);
		n /= b;

		if (n < b)
		{
			v.push_back(n);
			break;
		}
	}
}

int NimSum(int b, int x, int y)
{
	if (x < y)
		swap(x, y);
	vector<int> v1, v2;
	func(v1, x, b);
	func(v2, y, b);

	for (int i = 0; i < v2.size(); i++)
	{
		v1[i] += v2[i];
		v1[i] %= b;
	}

	int ret = 0;
	for (int i = 0; i < v1.size(); i++)
		ret += v1[i] * pow(b, i);

	return ret;
}

int main(void)
{
	int t;
	cin >> t;

	while (t--)
	{
		int b, x, y;
		cin >> b >> x >> y;
		cout << NimSum(b, x, y) << '\n';
	}

	return 0;
}