[백준 3460] 이진수

문제 (Bronze 3)

양의 정수 n이 주어졌을 때, 이를 이진수로 나타냈을 때 1의 위치를 모두 찾는 프로그램을 작성하시오. 최하위 비트(least significant bit, lsb)의 위치는 0이다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. (1 ≤ T ≤ 10, 1 ≤ n ≤ 10^6)

출력

각 테스트 케이스에 대해서, 1의 위치를 공백으로 구분해서 줄 하나에 출력한다. 위치가 낮은 것부터 출력한다.

문제 풀이

이번 문제는 N을 이진수로 변환한 후 1인 자릿수를 출력하는 문제이다. 일반적으로 십진수를 이진수로 변환하는 코드는 다음과 같다.

string decimal_to_binary(int N) {
    string ret = "";
    
    while(N) {
        ret += to_string(N % 2);
        N /= 2;
    }
    
    return string(ret.rbegin(), ret.rend());
}

위의 코드를 보면 return을 할 때 string을 뒤집어 주는 것을 볼 수 있다.
즉, 처음 (N % 2)를 한 결과가 lsb(least significant bit)인 것이다.

lsb의 위치가 0이므로 자릿수를 나타내는 int 변수를 선언 해 (N % 2)이 결과가 1일 경우 현재 자릿수를 출력하도록 하여 문제를 해결하였다.

코드

#include <iostream>

using namespace std;

void solution(int N) {
    int digit = 0;
        
    while(N) {
        if(N % 2 == 1) cout << digit << " ";
        N /= 2;
        digit++;
    }
}

int main() {
    int T, N;
    cin >> T;
    for(int i=0; i<T; ++i) {
        cin >> N;
        solution(N);
    }
    
    return 0;
}

문제 링크

3460번: 이진수