글 읽기 - 2464번 비밀번호 문제 예외가 뭘까요 ?

hist0613 9년 전 1

일단 입력받은 숫자를 문자열로 만들어서

그보다 작은 수는

가장 오른쪽의 0과, 0 이후에 처음으로 나타난 1의 위치를 바꿔주는 방법으로 구했고

그보다 큰 수는

가장 오른쪽의 1과, 1 이후에 처음으로 나타난 0의 위치를 바꿔주는 방법으로 구했습니다

각각의 예외 처리는 자릿수가 바뀌는 경우를 생각했습니다.

제가 생각하지 못 한 예외가 뭐가 있을까요 ㅜㅜ

또, 이 문제는 테스트 코드를 어떤 식으로 만들어야 할지 조언 좀 주시면 감사하겠습니다!

// binary string -> long long
long long parse_int(string a){
	long long ret = 0;
	for(int i = 0 ; i < a.size(); i++) ret = ret * 2 + (a[i] - '0');
	return ret;
}

int main(void){
	long long A;
	cin>>A;

	int cnt = 0;
	string bin = "";
	while(A){
		cnt += A%2;
		bin = bin + to_string(A%2);
		A /= 2;
	}
	bin = string(bin.rbegin(), bin.rend());

	long long lower = 0, upper = 0;
	string bin_lower = bin, bin_upper = bin;

	int right = -1, flag = 0;
	// 가장 오른쪽의 0과, 0 이후에 처음으로 나타난 1의 위치를 바꿔줌
	for(int i = bin_lower.size()-1; i >= 0; i--){
		if(bin_lower[i] == '0') right = i;
		else if(right != -1 && bin_lower[i] == '1'){
			swap(bin_lower[i], bin_lower[right]);
			flag = 1;
			break;
		}
	}
	// 바꿀 수 있는 경우
	// 1111 과 같은 경우에는 flag 가 0 이라서 자동으로 0이 출력됨
	if(flag == 1){
		// 길이가 변하는 경우 10111 -> 01111 등
		if(bin_lower[0] == '0'){
			bin_lower = "";
			for(int i = 0; i < cnt; i++) bin_lower += "1";
			for(int i = 0; i < bin.size() - cnt - 1; i++) bin_lower += "0";
		}
		lower = parse_int(bin_lower);
	}

	right = -1; flag = 0;
	// 가장 오른쪽의 1과, 1 이후에 처음으로 나타난 0의 위치를 바꿔줌
	for(int i = bin_upper.size()-1; i >= 0; i--){
		if(bin_upper[i] == '1') right = i;
		else if(right != -1 && bin_upper[i] == '0'){
			swap(bin_upper[i], bin_upper[right]);
			flag = 1;
			break;
		}
	}
	if(flag == 1) upper = parse_int(bin_upper);
	else{
		// 길이가 변하는 경우 1111 -> 10111 등
		bin_upper = "1";
		for(int i = 1; i <= bin.size() - cnt + 1; i++) bin_upper += "0";
		for(int i = 1; i <= cnt - 1; i++) bin_upper += "1";
		upper = parse_int(bin_upper);
	}

	cout<<lower<<' '<<upper<<endl;

	return 0;
}

pichulia 9년 전 4

1100000111 보다 작은 수 중 가장 큰 수는

1011110000 입니다.

즉, 이진 숫자 2개만 바꾼다고 해서 A보다 작은 수 중 "가장 큰 수"가 결정되는 것은 아닙니다. 무언가가 좀 더 필요하죠...

뭐, 비슷한 원리로

1100000111 보다 큰 수중 가장 작은 수는

1100001011 이고요

A보다 작은 이진수 중 가장 큰 수는, 작은 자리수부터 보다가 1이 나오면 그걸 0으로 만들어주고 그 뒤에 나머지를 전부 1로 만들어주면 될 것 같아요. A보다 큰 이진수 중 가장 작은 수는, 작은 자리수부터보다가 0이 나오면 1로 만들어주고 그 뒤에 나머지를 0으로 만들어주면 될 것 같구요. 하지만 저는 #include <algorithm>에 있는 next_permutation과 prev_permutation을 써서 문제를 해결했어요.

hist0613 9년 전 0

헐.................................................. 그런 방법이..............................................................

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

문제

문제

출처

ICPC

2464번 비밀번호 문제 예외가 뭘까요 ?

hist0613 9년 전 1

pichulia 9년 전 4

hist0613 9년 전 0

h0ngjun7 9년 전 2

hist0613 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말