문제 개요
이 문제에서는 두 개의 수가 주어지며, 두 수의 밑(진법)은 모두 n입니다. 목표는 두 수를 더한 결과를 역시 n진수 형태로 구하는 것입니다.
가장 직관적인 해결 방법은 다음 세 단계로 진행하는 것입니다.
- 주어진 n진수 두 개를 각각 10진수로 변환합니다.
- 10진수 값끼리 단순히 더합니다.
- 덧셈 결과를 다시 n진수로 변환하여 출력합니다.
n진수는 문자열(string) 형태로 입력받습니다. 그 이유는 밑이 9보다 큰 진법에서는 한 자릿수를 표현하기 위해 알파벳이 필요하기 때문입니다. 대표적인 예로 16진수는 10~15에 해당하는 값을 나타낼 때 6개의 문자(A~F)를 사용합니다.
입력 및 출력 예시
입력:
밑(진법): 16
첫 번째 수: 2C
두 번째 수: 5F
출력:
덧셈 결과: 8B
예시를 살펴보면, 16진수 2C는 10진수로 44이고, 5F는 95입니다. 두 수의 합은 139이며, 이를 다시 16진수로 변환하면 8B가 됩니다.
알고리즘
1. baseNtoDec(number, base)
입력: N진수 문자열, 밑 N의 값
출력: 해당 N진수와 동일한 10진수 값
Begin
len := length of number
power := 1
num := 0
for i := len -1 down to 0, do
if number[i] >= base, then
return invalid number
num := num + number[i] * power
power := power * base
done
return num
End
이 함수는 가장 오른쪽 자릿수부터 왼쪽으로 이동하며 각 자릿값에 자리 가중치(power)를 곱해 누적합니다. 처리 과정에서 특정 자릿값이 밑보다 크거나 같으면 유효하지 않은 수로 판단합니다.
2. decToBaseN(dec, base)
입력: 10진수, 변환할 밑 N
출력: N진수로 표현된 문자열
Begin
while dec > 0, do
res := concatenate (dec mod base) with res
dec := dec / base
done
reverse the result
return res
End
10진수를 N진수로 바꿀 때는 수를 밑으로 나눈 나머지를 차례대로 기록하고, 몫이 0이 될 때까지 반복합니다. 나머지는 낮은 자릿수부터 생성되므로 마지막에 문자열을 뒤집어야 올바른 결과를 얻을 수 있습니다.
3. addBaseN(num1, num2, base)
입력: N진수 두 개, 밑 N의 값
출력: 두 수의 덧셈 결과(N진수)
Begin
dec1 := baseNtoDec(num1, base)
dec2 := baseNtoDec(num2, base)
sum := decToBaseN(dec1 + dec2, base)
return sum
End
C++ 구현 예제
#include<iostream>
#include<algorithm>
using namespace std;
int getVal(char c) {
if(c >= '0' && c<='9')
return int(c-'0'); // 숫자 문자('0'~'9')의 10진수 값 반환
else
return int(c-'A'+10); // 알파벳 문자(A~F)는 10 이상의 값으로 변환
}
char revVal(int n) {
if(n >= 0 && n <=9)
return char(n+'0'); // 정수를 문자로 변환
else
return char(n+'A'-10); // 10 이상의 값은 알파벳으로 변환
}
int baseNtoDec(string number, int base) {
int len = number.size();
int power = 1;
int num = 0;
for(int i = len-1; i>= 0; i--) { // 마지막 자릿수부터 첫 자릿수까지 탐색
if(getVal(number[i]) >= base)
return INT_MIN; // 자릿값이 밑보다 크거나 같으면 오류 값 반환
num += getVal(number[i])*power;
power = power*base;
}
return num;
}
string decToBaseN(int dec, int base) {
string res = ""; // 빈 문자열로 초기화
while(dec > 0) {
res += revVal(dec%base);
dec /= base;
}
reverse(res.begin(), res.end()); // 문자열을 뒤집어 최종 답 도출
return res;
}
int main() {
int base;
string num1, num2, sum;
cout << "Enter Base: "; cin >> base;
cout << "Enter first number in base "<<base<<": ";cin >> num1;
cout << "Enter second number in base "<<base<<": ";cin >> num2;
sum = decToBaseN((baseNtoDec(num1, base) + baseNtoDec(num2, base)), base);
cout << "The result of addition is: " << sum;
}
실행 결과
Enter Base: 16
Enter first number in base 16: 2C
Enter second number in base 16: 5F
The result of addition is: 8B