[백준/BOJ] 2464번 비밀번호 (C/C++)

백준 온라인 저지(BOJ) 2464번 비밀번호
https://www.acmicpc.net/problem/2464

2464번: 비밀번호

* 사용언어 : C언어, C++

 

1. 문제

양의 정수 A (1 ≤ A ≤ 10^18) 의 이진수 표현에서 나오는 1의 개수 x 파악하고,
A 와 가장 인접하면서 1의 개수가 x 와 같은 두 수를 출력 (작은 수, 큰 수)

 

2. 풀이

bitwise 연산자와 bit mask 기법에 대한 이해가 필요한 문제입니다.
그리고 십진수를 이진수로 바꾸어 생각할 줄 알아야 합니다.
(아래 풀이에서는 이진수를 대괄호 안에 작성했습니다)

처음에 감이 안와서 일단 naive 한 버전으로 풀어보았습니다.
숫자 A 의 [1]의 개수를 미리 파악해두고
A 에서 +1, -1 을 각각 반복하면서 각 숫자의 [1]의 개수를 모두 세서 직접 비교하는 방식이었습니다.
풀이는 단순했지만 제출해보니 시간 초과가 났습니다.

하지만 naive 버전을 작성하면서 문제를 더 쉽게 이해할 수 있었고,
이를 기반으로 아래와 같이 시간 내에 동작하는 코드를 설계할 수 있었습니다.

 

1. 가장 낮은 비트부터 한 칸 씩 올라가면서 [01] or [10] 을 찾음 (1, 2, 4, 8, 16, ...)
   • [00] 과 [11] 은 정답을 찾는 데에 도움이 안되므로 skip
   • 해당 탐색 시 비트 [1] 의 개수를 미리 파악함 (3. 에서 사용)
2. bit mask 를 사용하여 [01] 는 [10] 으로, [10] 은 [01] 로 바꿈 ([11] 과 XOR 연산 활용)
   • 1의 개수를 유지한 채로 큰 수, 작은 수를 쉽게 만듬
   • 단, 가장 가까운 값은 아님 (예시. 9[1001]로 작은 수를 만들면 5[0101]가 되는데, 정답은 6[0110])
3. 가장 가까운 값을 만들기 위해 bit mask 이하 숫자를 재배열
   • bit masking 한 위치 이하의 값을 모두 [0] 으로 만듦 (/, * 연산자 활용)
   • 삭제된 [1] 을 미리 Count 한 만큼만 한 쪽에 몰아서 추가
     • 큰 수는 오른쪽에 몰아서 기록(큰 수 중 가장 작게)
     • 작은 수는 왼쪽에 몰아서 기록(작은 수 중 가장 크게)

이하 설명은 아래 소스 코드로 대체하겠습니다.
풀이가 쉽게 이해되지 않더라도 코드를 뜯어보면서 본인 것으로 만들면 좋겠습니다.

더 좋은 방식의 풀이가 있다면 댓글로 공유 부탁드립니다.

 

3. 코드

1) 시간 초과 (naive 버전)

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <cstdio>
using LL = long long;

LL A, LA, HA; // lower A, higher A
int cnt;

int countOne(LL n) {
	int cnt = 0;
	while (n) {
		if (n & 1) ++cnt;
		n >>= 1;
	}
	return cnt;
}

void nearestHigher() {
	HA = A + 1;
	while (HA > (1 << 60)) {
		if (countOne(HA) == cnt) return;
		++HA;
	}
	return;
}

void nearestLower() {
	LA = A - 1;
	while (LA) {
		if (countOne(LA) == cnt) return;
		--LA;
	}
	return;
}

int main(){
	scanf("%lld", &A);
	cnt = countOne(A);
	nearestLower();
	nearestHigher();

	printf("%lld %lld\n", LA, HA);
	return 0;
}

 

2) 통과

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <cstdio>
using LL =  long long;

LL A, HA, LA; // higher A, lower A
int oneCnt; // bit masking 전 까지 1의 개수
LL one = 1, mask = 3; // 1(2), 11(2)

void getNearestLower() {
	LA = A ^ mask; // 10 -> 01
	LA = LA / one * one; // 이하 버리기
	LL n = (one >> 1); // 왼쪽부터 1 채우기
	int cnt = oneCnt;
	while (n && cnt--) {
		LA += n;
		n >>= 1;
	}
}

void getNearestHigher() {
	HA = A ^ mask; // 01 -> 10
	HA = HA / one * one; // 이하 버리기
	LL n = 1; // 오른쪽부터 1 채우기
	int cnt = oneCnt;
	while (n < one && cnt--) {
		HA += n;
		n <<= 1;
	}
}

int main() {
	scanf("%lld", &A);
	while (1) {
		if (LA && HA) break;
		if (one > A) break;

		if ((A & mask) == (one << 1)) getNearestLower();
		if ((A & mask) == one) getNearestHigher();
		if (A & one) ++oneCnt;

		one <<= 1;
		mask <<= 1;
	}
	printf("%lld %lld\n", LA, HA);
	return 0;
}

* long long int 입출력 : %lld, int 입출력 : %d