백준 15740번 A+B - 9 (C++)

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

15740번: A+B - 9

Java나 Python으로 풀면 가뿐히 풀 수 있는 문제이지만 여태까지 C++로 풀어왔기 때문에 C++로 푼 문제였습니다.

코드에도 자세한 주석을 달아놨지만 이 문제를 풀기 위해서는 문자열로 입력받은 숫자들을 더하고 뺄 수 있어야 합니다.

 

덧셈 알고리즘은 아래와 같습니다. (add 함수)

0. 두 개의 BigInteger A와 B가 있다고 가정하겠습니다.

1. A와 B의 덧셈 결과의 길이는 최소 A와 B 중 더 큰 숫자의 길이이기 때문에 결괏값을 정의해줄 result 문자열의 길이를 A와 B 중 더 큰 문자열의 길이로 정의하고 각 자리를 모두 0으로 초기화합니다.

2. 끝자리부터 더해나가는데 이전 자리의 덧셈 결과에 carry가 존재하는지 확인 후 carry까지 더해줍니다.

(carry를 모를 경우 다음 링크를 참고해주세요! en.wikipedia.org/wiki/Carry_(arithmetic))

3. 마지막 자리까지 계산했는데도 carry가 존재한다면 result 문자열 맨 앞에 1을 추가해줍니다.

(예를 들자면 999 + 1 = 1000과 같은 경우)

 

뺄셈 알고리즘은 조금 더 복잡합니다. (subtract 함수)

0. 마찬가지로 BigInteger A와 B가 있다고 가정하겠습니다.

그리고 해당 알고리즘은 부호와 상관없이 절댓값 기준 더 큰 수로부터 작을 수를 빼는 함수입니다.

1. isFormerBiggerThanLatter 함수를 통해 B가 A보다 절댓값 기준으로 더 큰 경우 A와 B 값을 swap 해줍니다.

2. A와 B 문자열을 뒤집어주고 더 큰 수로부터 작은 수를 빼는 함수이므로 result 문자열을 A로 초기화해줍니다.

3. 앞자리부터 뺄셈을 진행하는데(뒤집어줬으므로 실제로는 맨 뒷자리부터) 이전 자리의 뺄셈 결과에 carry가 존재하는지 확인 후 carry까지 빼줍니다.

4. 마지막 자리까지 계산했는데도 carry가 존재한다면 result 문자열 마지막 자리(뒤집어줬으므로 실제로는 맨 앞자리) 숫자를 1 빼줍니다.

5. result 문자열을 다시 뒤집어주고 최초로 0이 아닌 인덱스를 찾아줍니다.

6. 5번에서 최초로 0이 아닌 인덱스를 찾았다면 최초로 0이 아닌 자리부터의 숫자들을 반환해주고, 찾지 못했다면 "0"을 반환해줍니다.

(결과가 다음과 같은 경우가 있을 수 있으므로: "00000000", "0001000") 

 

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

1. A와 B가 둘 다 양수일 경우 단순히 A와 B를 더해줍니다.

 

2. A와 B가 모두 음수일 경우 절댓값 A와 절댓값 B를 더해주고 해당 결과의 음수 값을 출력해줍니다.

 

3. A는 양수인데 B는 음수인 경우 아래와 같은 조건을 확인해줘야 합니다.

* 절댓값 기준 A가 B보다 큰가?

* 연산 결과가 0인가

3.1 절댓값 기준 A가 B보다 크거나 연산 결과가 0인 경우 결괏값을 그대로 출력해줍니다.

3.2 그렇지 않은 경우 음수 처리를 한 뒤 결과를 출력해줍니다.

 

4. A는 음수인데 B는 양수인 경우도 마찬가지로 3번과 같은 조건을 확인해줘야 합니다.

4.1 절댓값 기준 A가 B보다 크거나 연산 결과가 0이 아닌 경우 음수 처리를 한 뒤 결과를 출력해줍니다.

4.2 그렇지 않은 경우 결괏값을 그대로 출력해줍니다.

 

 

 

 

개발환경:Visual Studio 2017

 

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