글 읽기 - 반례를 알고 싶습니다.

adfsfsf 5년 전 0

big integer를 구현해서 풀었습니다. 예제인 4도 잘 나오고, 500,000,000,000의 값도 잘 출력됩니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(void)
{
	unsigned long long int n, i, len, j, len2, len1, c;
	string s, sum = "0", now = "1", ss;//s는 입력받은 수를 뒤집힌 2진법으로 변환한 배열입니다. 1이 들어오면 s는 "1"이 되며 sum은 1이 됩니다. 2가 들어오면 s는 "01"이 되고, now가 1일 때 sum에 더해지지 않고 now가 3일 때 sum에 더해져 sum이 3이 됩니다.
	cin >> n;
	now[0] -= '0';
	sum[0] -= '0';
	while (n > 1)
	{
		if ((n % 2) == 1)
			s += "1";
		else
			s += "0";
		n /= 2;
	}
	if (n == 1)
		s += "1";
	len = s.length();
	for (i = 0; i < len; i++)
	{
		len1 = sum.length();
		len2 = now.length();
		if (s[i] == '1')//sum에 now를 더한다.
		{
			c = 0;
			if (len1 > len2)
			{
				for (j = 0; j < len2; j++)//sum에 직접 합을 저장
				{
					sum[len1 - j - 1] = sum[len1 - j - 1] + now[len2 - j - 1];
					if (j != 0)
					{
						sum[len1 - j - 1] += (sum[len1 - j] / 10);
						sum[len1 - j] %= 10;
					}
					if (j == (len1 - 1))
						c = (sum[0] / 10);
				}
				for (j = 0; j < (len1 - len2); j++)
				{
					if (sum[len1 - len2 - j] > 10)
					{
						if (j == (len1 - len2 - 1))
							c = (sum[0] / 10);
						sum[len1 - len2 - j - 1] += sum[len1 - len2 - j] / 10;
						sum[len1 - len2 - j] %= 10;
					}
					else
						break;
				}
				if (c != 0)
				{
					sum[0] %= 10;
					sum = to_string(c) + sum;
					sum[0] -= '0';
				}
			}
			else if (len1 < len2)//sum이 더 짧으면
			{
				ss = "" + now;
				for (j = 0; j < len1; j++)//ss에 합을 저장 후 sum으로 이동
				{
					ss[len2 - j - 1] += sum[len1 - j - 1];
					if (j != 0)
					{
						ss[len2 - j - 1] += ss[len2 - j] / 10;
						ss[len2 - j] %= 10;
					}
				}
				for (j = 0; j < (len2 - len1); j++)
				{
					if (ss[len2 - len1 - j] > 10)
					{
						if (j == (len2 - len1 - 1))
							c = (ss[0] / 10);
						ss[len2 - len1 - j - 1] += ss[len2 - len1 - j] / 10;
						ss[len2 - len1 - j] %= 10;
					}
					else
						break;
				}
				if (c != 0)
				{
					ss[0] %= 10;
					ss = to_string(c) + ss;
					ss[0] -= '0';
				}
				sum = "" + ss;
			}
			else//sum과 now의 길이가 같으면
			{
				ss = "" + now;
				for (j = 0; j < len1; j++)//ss에 합을 저장 후 sum으로 이동
				{
					ss[len2 - j - 1] += sum[len1 - j - 1];
					if (j != 0)
					{
						ss[len2 - j - 1] += ss[len2 - j] / 10;
						ss[len2 - j] %= 10;
					}
					if (j == (len1 - 1))
					{
						c = ss[0] / 10;
						ss[0] %= 10;
					}
				}
				if (c != 0)
				{
					ss = to_string(c) + ss;
					ss[0] -= '0';
				}
				sum = "" + ss;
			}
		}
		c = 0;
		for (j = 0; j < len2; j++)//now를 3배 한다.
		{
			now[len2 - j - 1] *= 3;
			if (j != 0)
			{
				now[len2 - j - 1] += now[len2 - j] / 10;
				now[len2 - j] %= 10;
			}
			if (j == (len2 - 1))
				c = (now[len2 - j - 1] / 10);
		}
		if (c != 0)
		{
			now[0] %= 10;
			now = to_string(c) + now;
			now[0] -= '0';
		}
	}
	len = sum.length();
	for (i = 0; i < len; i++)
		sum[i] += '0';
	cout << sum<< endl;
	return 0;
}

adfsfsf 5년 전 0

s를 이용한 이유는 n을 이진법올 바꾼 경우 3의 거듭제곱들을 3^i가 사용되면 1, 안 사용되면 0으로 표현되기 때문입니다.

소스에도 적었듯, s의 i번째 원소는 3^i가 더해지는지 여부를 나타냅니다.

doju 5년 전 0

len1 < len2인 경우를 처리하는 부분에 오타가 있습니다. 반례로는 10이 있습니다.

adfsfsf 5년 전 0

@doju

그렇네요. 제가 >=10이라 해야 할 걸 >10으로 했군요. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 알고 싶습니다.

adfsfsf 5년 전 0

adfsfsf 5년 전 0

doju 5년 전 0

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말