백준 8437번 Julka (C++)

문제 링크입니다: www.acmicpc.net/problem/8437

8437번: Julka

문제가 폴란드어인데 파파고에서는 폴란드어를 지원하지 않으므로 구글 번역기를 사용하시길 바랍니다.

 

기존의 백준 2338번 긴 자리 계산(jaimemin.tistory.com/1552)과 유사한 문제였는데 양수 나눗셈까지 구현해야 하는 문제였습니다.

물론, BigInteger를 지원하는 Java와 Python으로 푸시면 금방 풀 수 있는 문제였습니다.

 

BigInteger에 대해 2로 나누는 알고리즘은 아래와 같습니다. (divideByTwo)

1. 초등학교 때 배운대로 앞에서부터 나눗셈을 진행하는데,

 

2. 나눗셈을 진행하는 자리의 숫자가 무엇이냐에 따라 다르게 접근해야 합니다.

 

2.1 해당 자리의 숫자가 0이라면 result 문자열에 0을 더하고 다음 자리 수에 대해 나눗셈을 진행할 수 있도록 idx를 1 증가시켜줍니다.

 

2.2 해당 자리의 숫자가 1이라면 다음 자리 숫자까지 빌려와서 십의 자리 숫자에 대해 나눗셈을 진행해줘야 합니다.

2.2.1 숫자를 빌려왔으므로 result 문자열에 0을 더해줘야 하는데, 여기서 중요한 건 이 숫자 1이 전에 진행한 나눗셈의 잔여물이라면 0을 더해주면 안 됩니다.

ex) 전자에 대한 예시: 1010 / 2 = 505, 후자에 대한 예시: 112 / 2 = 56

2.2.2 이후에는 학교에서 배운 대로 나눗셈을 진행해주고 2.2.1에서 0을 더해줄지 말지를 판별하기 위해 num - (몫 * 2)가 1일 경우 flag를 true로 설정해줍니다.

 

2.3 2.2.2와 똑같이 진행해주면 됩니다.

 

3. 앞에 불필요한 0을 제거한 result 문자열을 반환해줍니다.

 

전체적인 알고리즘은 아래와 같습니다.

1. 입력받는 숫자 두 개가 전체 사과의 개수, 그리고 두 소녀가 가지고 있는 사과 개수의 차이입니다.

2. 따라서 소녀들이 가지고 있는 사과의 개수를 구하기 위해서는 방정식을 세워야 합니다.

* 방정식: (소녀 2가 가지고 있는 사과의 개수 + 차이) + (소녀2가 가지고 있는 사과의 개수) = (전체 사과의 개수)

3. 2번에서 세운 방정식을 풀고 소녀 1이 가지고 있는 사과의 개수와 소녀 2가 가지고 있는 사과의 개수를 출력해주면 됩니다.

	#include <iostream>
	#include <string>
	#include <algorithm>
	using namespace std;
	// 앞에 불필요한 0을 제거
	string getResultWithoutUnnecessaryZeros(string result)
	{
	// 최초로 0이 아닌 인덱스를 찾는다
	int firstNonZeroIdx = result.size();
	for (int i = 0; i < result.size(); i++)
	{
	if (result[i] != '0')
	{
	firstNonZeroIdx = i;
	break;
	}
	}
	// 모든 자리가 0이라면 0을 반환
	if (firstNonZeroIdx == result.size())
	{
	return "0";
	}
	// 최초로 0이 아닌 자리부터의 숫자들을 반환
	return result.substr(firstNonZeroIdx);
	}
	// bigInteger 덧셈 함수
	string add(string s1, string s2)
	{
	// 덧셈의 결과 길이는 최소 s1과 s2 중 더 큰 숫자의 길이
	string result(max(s1.size(), s2.size()), '0');
	bool carry = false;
	// 끝에부터 더해 나감
	for (int i = 0; i < result.size(); i++)
	{
	int temp = carry;
	carry = false;
	if (i < s1.size())
	{
	temp += s1[s1.size() - i - 1] - '0';
	}
	if (i < s2.size())
	{
	temp += s2[s2.size() - i - 1] - '0';
	}
	if (temp >= 10)
	{
	carry = true;
	temp -= 10;
	}
	result[result.size() - i - 1] = temp + '0';
	}
	// 마지막에도 캐리가 있다면 맨 앞에 1 추가
	if (carry)
	{
	result.insert(result.begin(), '1');
	}
	return getResultWithoutUnnecessaryZeros(result);
	}
	// s1이 s2보다 큰 지 여부를 판별하는 함수
	bool isFormerBiggerThanLatter(string s1, string s2)
	{
	if (s1.size() != s2.size())
	{
	return s1.size() > s2.size();
	}
	for (int i = 0; i < s1.length(); i++)
	{
	if (s1[i] == s2[i])
	{
	continue;
	}
	return s1[i] > s2[i];
	}
	return true;
	}
	// bigInteger 뺄셈 함수 (부호는 판별 X)
	string subtract(string s1, string s2)
	{
	// 절댓값 기준 s1과 s2 중 더 큰 수로부터 더 작은 수를 빼는 함수이므로
	if (isFormerBiggerThanLatter(s1, s2) == false)
	{
	swap(s1, s2);
	}
	// s1과 s2를 거꾸로 뒤집는다
	reverse(s1.begin(), s1.end());
	reverse(s2.begin(), s2.end());
	// 더 큰 수로부터 더 작은 수를 빼므로 add 함수와 달리 result를 s1으로 초기화
	string result = s1;
	int carry = 0;
	for (int i = 0; i < result.size(); i++)
	{
	int tempCarry = carry;
	carry = 0;
	// carry가 존재한다면 s1[i]로부터 1 뺌
	int temp = (s1[i] - '0') - tempCarry;
	// 음수가 된다면 carry가 존재한다고 표시 후 10을 더해줌
	if (temp < 0)
	{
	carry = 1;
	temp += 10;
	}
	if (i < s2.size())
	{
	temp -= (s2[i] - '0');
	if (temp < 0)
	{
	carry = 1;
	temp += 10;
	}
	}
	result[i] = temp + '0';
	}
	// carry가 있다면 마지막 자리 숫자 1 빼줌
	if (carry)
	{
	int lastDigit = result[result.size() - 1];
	lastDigit--;
	result[result.size() - 1] = lastDigit + '0';
	}
	// 다시 뒤집어준 뒤
	reverse(result.begin(), result.end());
	return getResultWithoutUnnecessaryZeros(result);
	}
	//bigInteger 곱셈 구현
	string multiply(string s1, string s2)
	{
	string result = "0";
	// 곱셈 과정을 그대로 구현
	for (int i = 0; i < s2.size(); i++)
	{
	string line(s1);
	int carry = 0;
	for (int j = s1.size() - 1; j >= 0; j--)
	{
	int temp = carry;
	carry = 0;
	temp += (s1[j] - '0') * (s2[s2.size() - (i + 1)] - '0');
	if (temp >= 10)
	{
	carry = temp / 10;
	temp %= 10;
	}
	line[j] = temp + '0';
	}
	if (carry > 0)
	{
	line.insert(line.begin(), carry + '0');
	}
	// 곱셈 과정을 생각해보면 0을 뒤에 붙여주는 이유를 알 것입니다.
	line += string(i, '0');
	result = add(result, line);
	}
	return getResultWithoutUnnecessaryZeros(result);
	}
	// 양수 나눗셈
	string divideByTwo(string s)
	{
	string result;
	// s 문자열 인덱스
	int idx = 0;
	// 각 자리 나눗셈을 진행하기 위한 변수
	int num = 0;
	// 나눗셈 몫
	int quotient = 0;
	// 다음 자리 숫자까지 빌려와서 나눗셈을 했는데
	// 해당 자리에서 다시 나눗셈을 진행해야하는 경우
	bool flag = false;
	while (idx != s.length())
	{
	int num = s[idx] - '0';
	switch (num)
	{
	case 0:
	result += '0';
	idx++;
	break;
	case 1:
	num = num * 10 + s[idx + 1] - '0';
	quotient = num / 2;
	if (flag == false)
	{
	result += '0';
	}
	else
	{
	flag = false;
	}
	result += quotient + '0';
	num -= (quotient * 2);
	s[++idx] = num + '0';
	if (num % 2 == 0)
	{
	idx++;
	}
	else
	{
	flag = true;
	}
	break;
	default:
	quotient = num / 2;
	result += (num / 2) + '0';
	num -= quotient * 2;
	s[idx] = num + '0';
	if (s[idx] == '0')
	{
	idx++;
	}
	else
	{
	flag = true;
	}
	}
	}
	return getResultWithoutUnnecessaryZeros(result);
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string total, diff;
	cin >> total >> diff;
	string totalMinusDiff = subtract(total, diff);
	string secondAnswer = divideByTwo(totalMinusDiff);
	string firstAnswer = add(secondAnswer, diff);
	cout << firstAnswer << "\n" << secondAnswer << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~