정수 N이 입력으로 주어졌을 때, N 이하의 숫자 중에서 자릿수가 오직 0과 1로만 이루어진 수(2진수 형태의 숫자)가 몇 개 있는지 구하는 것이 이 문제의 목표입니다. 예를 들어 입력 N이 12라면, 조건을 만족하는 수는 1, 10, 11로 총 3개이므로 답은 3이 됩니다.
예시
입력
N=100
출력
N 이하의 2진수 형태 숫자의 개수: 4
설명
100 이하의 2진수 형태 숫자: 1, 10, 11, 100
입력
N=120
출력
N 이하의 2진수 형태 숫자의 개수: 7
설명
120 이하의 2진수 형태 숫자: 1, 10, 11, 100, 101, 110, 111
알고리즘 접근 방식
이 문제는 정수 벡터(vec)를 활용한 생성 및 탐색 방식으로 효율적으로 해결할 수 있습니다. 먼저 벡터에 1을 넣고, 마지막에 저장된 값(temp)을 꺼낸 뒤 temp*10과 temp*10+1을 곱하고 더하는 방식으로 다음 숫자를 생성합니다. 2진수 형태의 숫자는 항상 1, 10, 11, 100, 110, 111처럼 규칙적인 나열을 이루기 때문에 이 방법으로 모든 후보를 빠짐없이 만들어 낼 수 있습니다. 벡터에서 숫자를 하나씩 꺼내면서 그 값이 N 이하이면 카운트를 증가시키고, N을 초과하는 값이 더 이상 없을 때까지 반복합니다.
- 정수 N을 입력받습니다.
- 함수 Smaller_N(int N)은 N을 전달받아 N 이하의 2진수 형태 숫자의 개수를 반환합니다.
- 초기 카운트(count)를 0으로 설정합니다.
- 0과 1로만 이루어진 정수를 저장할 정수 벡터 vec을 선언합니다.
- vec.push_back(1)을 사용해 벡터에 첫 번째 값인 1을 추가합니다.
- while 루프를 돌면서 vec.back()으로 마지막에 넣은 값을 temp에 꺼낸 뒤, vec에서 제거합니다.
- temp가 N 이하라면 count를 1 증가시키고, temp*10과 temp*10+1로 다음 2진수 형태의 정수 두 개를 생성해 vec에 추가합니다.
- while 루프가 종료되면 count를 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int Smaller_N(int N){
int count = 0;
vector<int> vec;
vec.push_back(1);
while (!vec.empty()){
int temp = vec.back();
vec.pop_back();
if (temp <= N){
count++;
int temp_2 = temp * 10;
vec.push_back(temp_2);
vec.push_back(temp_2 + 1);
}
}
return count;
}
int main(){
int N = 1000;
cout<<"Count of Binary Digit numbers smaller than N are: "<<Smaller_N(N);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of Binary Digit numbers smaller than N are: 8
N이 1000인 경우, 조건을 만족하는 숫자는 1, 10, 11, 100, 101, 110, 111, 1000으로 총 8개입니다. 이 알고리즘은 각 숫자를 한 번씩만 생성하고 처리하므로, 답의 개수에 비례하는 시간 복잡도로 동작하는 매우 효율적인 방법입니다.