C언어 백준 10757 큰수 A+B 풀이

https://www.acmicpc.net/problem/10757

10757번: 큰 수 A+B

 

문제

 

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

 

풀이

 

문제를 풀어본 결과, c언어에서 왜 이렇게 큰 자리 수를 출력하지 못하는지 그 원인에 대해서 파악하는 것이 가장 중요할 것이라고 판단. 따라서 이번 포스팅은 그 이유에 대해 중점적으로 설명할 것입니다.

 

오류

#include <stdio.h>

int main() {
	int A, B;
	scanf("%d %d", &A,&B);
	
	printf("%d", A + B);
	return 0;
}

일단 그냥 아무생각없이 이런 식으로 계산을 해보았는데요..

Q)이런식으로 -2라는 값이 도출되어버리는 것을 알 수 있습니다.. 도대체 왜그럴까요?

 

C/C++에는 담을 수 있는 자료형에 한계가 있기 때문입니다.

 

Q)어떻게 해결할까?

문자열 배열을 설정하고, 문자열끼리 더하는 알고리즘을 직접구현해 문제를 해결해야 합니다.

10^1 은 2자리/ 10^2 은 3자리/ ... 10^10000은 10001자리가 될 것입니다.

 

Q)reverse 함수 사용의 이유

위의 그림에서 보듯 자리수가 하나 증가하면, 배열의 인덱스들이 한칸 씩 모두 밀려나야 합니다.

reverse를 사용하면 뒤에 인덱스 하나만 추가해주면 되므로 훨씬 용이 합니다.

따라서 reverse 함수를 사용하는 것입니다.

 

Q)문자열을 세로로 계산할 때 기준이 되는 입력값이 가장 큰 수가 되어야하는 이유

예를들어 123 + 32 라고 하는 경우 세자리를 모두 계산해야하므로 큰 수를 기준으로 

차례로 계산을 합니다.

 

정답코드

#include <stdio.h>
#include <string.h>

void reverse(char arr[]) //문자열 역순 정렬
{
	int len = strlen(arr);
	for (int i = 0; i < len / 2; i++) 
	{
		char temp = arr[i];
		arr[i] = arr[len - i - 1];
		arr[len - i - 1] = temp;
	}
}

int main() {
	char A[10002] = { 0 };
	char B[10002] = { 0 };
	char res[10003] = { 0 };
	int carry = 0; //자리수 올림
	int len = 0;
	scanf("%s %s", A, B);

	reverse(A);
	reverse(B);

	if (strlen(A) > strlen(B)) //큰수 기준 
	{
		len = strlen(A);
	}
	else
	{
		len = strlen(B);
	}

	for (int i = 0; i < len; i++)
	{
		int sum = A[i] - '0' + B[i] - '0' + carry; //ASCII 코드 보며 이해할 것
		if (sum < 0)//자리수가 다를경우(sum < 0) sum은 -'0'이 한번 더 계산됨(둘중하나는 NULL이므로)
		{
			sum += '0';//그런경우 +'0'을 해서 맞춰준다.
		}
		if (sum > 9)
		{
			carry = 1; //더한것이 9를 넘어가면 그 다음자리수 +1 해줘야하므로
		}
		else
		{
			carry = 0;
		}
		printf("A[%d] = %c , B[%d] = %c\n", i, A[i], i, B[i]);//시각화를 위한 코드
		res[i] = sum % 10 +'0';
	}
	if (carry == 1)
	{
		res[len] = '1';
	}
	reverse(res); //180도 돌려놨던 것을 다시 180도 돌려 원상복구
	printf("%s", res);
	return 0;
}

배운점

1)배열이 한칸씩 밀리는 경우 코드 작성이 복잡해지므로

reverse함수를 활용하는 아이디어를 기억하자

 

2)for 문 과 하나의 변수를 통해 switch를 키고 켜듯이 판단하는 아이디어는

자주 사용된다.

ex)carry

 

3)배열의 마지막부분에서 sum > 9 일때를 판단해주는 것이므로

배열이 다 끝난 뒤 

그 밑에 if (carry == 1)의 조건문을 써준 아이디어도 꼭 기억하자.