글 읽기 - 매우 큰 수 덧셈,곱셈 문제..

sgc109 8년 전 0

처음엔 꼬지않은 단순한 문제라고 생각해서 단숨에 코드를 작성해서 예제 입력을 쳐넣어보았는데

4바이트로 표현할 수 있는 수를 초과 한것을 알게되어, 알고보니 long long 까지 초과해 버리는 경우도 있다는 것을 알았습니다.

그래서 일반적인 정수 계산으로는 안될것같아서(C++ 에 long long 보다 더 많은 바이트를 사용하여 정수계산을 하는 방법이있나요..?)

int 를 string 형태로 변환하여 계산하는 방법을 사용해야 겠다고 생각을 했습니다.

그래서 관련 STL 이 있나 구글링을 해봤는데 찾지못하여(만약 있다면 가르쳐주시면 감사하겠습니다) 직접 구현을 했습니다..

구현을 하여 제출을 해보니 틀렸다고 나왔습니다.. 허나 아무리 찾아봐도 틀린부분을 찾지 못하였기에 도움을 받고자 질문을 올립니다! 감사합니다.

+p.s. 그리고 보통 이런 문제의 경우 n 이 0 일 때 1가지로 보는것이 맞나요? 1가지 일 것 같기는 하나 혹시 몰라 0가지로 뜨게 만들어봐도 틀렸다고 나왔습니다..

@hongjun7

#define REP(i,a,b) for(int i = a; i < b; i++)
#define FOR(i,n) REP(i,0,n)

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

using namespace std;

string string_add(string a, string b) {
	string new_str = "";
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());

	string long_s;
	string short_s;
	if (a.size() >= b.size()) {
		long_s = a;
		short_s = b;
	}
	else{
		long_s = b;
		short_s = a;
	}
	int carry = 0;
	int dif = long_s.size() - short_s.size();
	FOR(i, dif)
		short_s += "0";
	FOR(i, long_s.size()) {
		int hab = stoi(long_s.substr(i, 1)) + stoi(short_s.substr(i, 1)) + carry;
		if (hab > 9) {
			carry = 1;
			hab -= 10;
		}
		else carry = 0;

		new_str += to_string(hab);
	}
	if(carry != 0) new_str += to_string(carry);
	reverse(new_str.begin(), new_str.end());
	return new_str;
}


string string_multi(string a, string b) {
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());

	string acc = "0";
	FOR(i, a.size()) {
		int carry = 0;
		string gob = "";
		FOR(j, b.size()) {
			int gob_1 = stoi(a.substr(i, 1)) * stoi(b.substr(j, 1)) + carry;
			gob += to_string(gob_1 % 10);
			carry = gob_1 / 10;
		}
		if (carry != 0) gob += to_string(carry);
		FOR(j, i)
			gob = "0" + gob;
		reverse(gob.begin(), gob.end());
		acc = string_add(acc, gob);
	}
	return acc;
}


int main() {

	int T;
	scanf("%d", &T);
	while (T--) {
		string count[251];
		count[0] = "1";
		count[1] = "1";

		int n;
		scanf("%d", &n);

		for(int i = 2; i <= n; i++) {
			count[i] = string_add(string_multi(count[i - 2], "2"), count[i-1]);
		}
//		count[0] = "0";
		printf("%s\n", count[n].c_str());
	}

	return 0;
}

h0ngjun7 8년 전 2

1. 테스트 케이스를 입력받으셨네요.

2. 2배하는 연산은 긴자리 덧셈으로 하셔야 더 빠르겠죠?

#define REP(i,a,b) for(int i = a; i < b; i++)
#define FOR(i,n) REP(i,0,n)

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

using namespace std;

string string_add(string a, string b) {
	string new_str = "";
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());

	string long_s;
	string short_s;
	if (a.size() >= b.size()) {
		long_s = a;
		short_s = b;
	}
	else{
		long_s = b;
		short_s = a;
	}
	int carry = 0;
	int dif = long_s.size() - short_s.size();
	FOR(i, dif)
		short_s += "0";
	FOR(i, long_s.size()) {
		int hab = stoi(long_s.substr(i, 1)) + stoi(short_s.substr(i, 1)) + carry;
		if (hab > 9) {
			carry = 1;
			hab -= 10;
		}
		else carry = 0;

		new_str += to_string(hab);
	}
	if (carry != 0) new_str += to_string(carry);
	reverse(new_str.begin(), new_str.end());
	return new_str;
}
int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		string count[251];
		count[0] = "1";
		count[1] = "1";
		for (int i = 2; i <= n; i++) {
			count[i] = string_add(string_add(count[i - 2], count[i - 2]), count[i - 1]);
		}
		printf("%s\n", count[n].c_str());
	}
	return 0;
}