백준 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가 가지고 있는 사과의 개수를 출력해주면 됩니다.

개발환경:Visual Studio 2017

 

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