문제 개요
이 튜토리얼에서는 이진 표현상 m개의 1과 m-1개의 0으로 구성된 숫자 중 n보다 작은 가장 큰 수를 찾는 프로그램을 C++로 작성해 보겠습니다.
예를 들어 m이 3이라면 이진수는 11100(십진수 28)처럼 1이 세 개, 0이 두 개인 형태가 됩니다. 목표는 주어진 n 미만의 범위에서 이런 조건을 만족하는 최댓값을 구하는 것입니다.
해결 방법
문제를 해결하는 단계는 다음과 같습니다.
- 두 변수 bits와 result를 각각 2와 1로 초기화합니다.
- 1부터 n까지 반복하는 루프를 작성합니다.
- 반복 변수의 값을 (pow(2, bits) - 1) * pow(2, bits - 1) 공식으로 갱신합니다.
- 반복 변수가 n보다 작으면 result를 해당 값으로 업데이트합니다.
- bits 값을 1씩 증가시킵니다.
- 최종 result를 반환합니다.
예제 코드
실제 동작하는 전체 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
long long getTheNumber(long long n) {
long bits = 2;
long long result = 1;
long long i = 1;
while (i < n) {
i = (int)(pow(2, bits) - 1) * (pow(2, bits - 1));
if (i < n) {
result = i;
}
bits++;
}
return result;
}
int main() {
long long n = 654;
cout << getTheNumber(n) << endl;
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
496
동작 원리
이 코드의 핵심은 비트 수를 하나씩 늘려가며 후보 숫자를 생성하는 것입니다. bits가 k일 때 후보 숫자는 k개의 연속된 1 뒤에 k-1개의 0이 붙은 형태입니다.
- bits = 2 → 110 (십진수 6)
- bits = 3 → 11100 (십진수 28)
- bits = 4 → 1111000 (십진수 120)
- bits = 5 → 111110000 (십진수 496)
n이 654일 경우, 654보다 작은 가장 큰 후보는 496입니다. 그다음 후보인 2016(11111100000)은 654를 초과하기 때문에 루프가 종료되고 496이 최종 결과로 반환됩니다.
결론
지금까지 이진 표현에서 m개의 1과 m-1개의 0으로 구성된 가장 큰 수를 찾는 방법을 알아보았습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.