Mystika+Algorithm

'알고리즘/문자열 처리'에 해당되는 글 1건

  1. BOJ 5893 - 17배

BOJ 5893 - 17배

알고리즘/문자열 처리

문제


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


풀이


들어오는 이진수의 길이의 최대가 1000자리라고 했으니 십진수로 변환하면 최대 $2^{1001}-1$ 값이 들어온다는 의미이므로 long long을 이용하더라도 범위를 초과하므로 해결 할 수가 없다. 게다가 C언어에서는 직접 2진수 인풋을 받을 수 없으므로 문자열로 입력받아 처리하는게 제일 간편할것이다.


쉬프트 연산으로 17배는 $ x << 4 + x $ 이므로 똑같이 계산해주면 된다.


문자열이므로 가장 왼쪽(0번 인덱스)은 직접 계산을 하지않았는데 계산하지 않은 0번 인덱스는 항상 1~4 사이의 값이 나오므로 계산 후에 [0]의 문자가 무엇인지 보고 직접 출력하게 했다.

#include <iostream>
#include <string>
using namespace std;
int main() {
	int i=0,respos;
	string s,shifted,res,z="";
	cin>>s;
	res = shifted = s +"0000"; //왼쪽으로 << 4 연산;
	respos=res.size();
	for(i=s.size()-1;i>=0;i--){
		respos--;
		if(s[i]=='0')  continue;
		res[respos]++;
	}
	for(i=res.size()-1;i>0;i--){
		if(res[i]>='2'){
			res[i-1] += (res[i]-'0')/2;
			res[i] = ((res[i]-'0')%2)+'0';

		}
	}
	if(res[0]=='2') res[0]='0',cout<<"1";
	else if(res[0]=='3') res[0]='1',cout<<"1";
	else if(res[0]=='4') res[0]='0',cout<<"10";
	cout<<res;
}


저작자 표시 비영리 변경 금지
신고