알고리즘(C++) / 백준 3460 : 이진수

3460 - 이진수

www.acmicpc.net/problem/3460

3460번: 이진수

문제

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

 

입력

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

 

출력

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

 

코드

//3460 이진수
#include <iostream>
using namespace std;

int main() {
	int T, n;
	cin >> T;
	int array[20]; //이진수 저장

	for (int i = 0; i < T; i++) {
		cin >> n;
		int k = 0;
		while (1) {
			if (n % 2 == 0) {
				array[k] = 0; //나머지 0
			}
			else
				array[k] = 1; //나머지 1
			n /= 2;
			k++;
			if (n == 1 || n == 0) {
				array[k] = n;
				break;
			}

		}
		for (int j = 0; j < k + 1; j++) {
			if (array[j] == 1) {
				cout << j << " ";
			}
		}
		cout << endl;
	}

	return 0;
	//13 = 1101 : 0 2 3 출력
}

결과

 

설명

1에서 1000000사이의 수를 입력하여 십진수를 이진수로 나타내는 문제이다. 

이진수로 나타냈을때 1의 위치를 모두 찾고 위치가 낮은 것부터 출력된다.

13은 이진수로 1101으로 나타낸다. 그러므로 출력은 위치가 낮은 것부터 0, 2, 3으로 출력되게 된다.

이때 array는 이진수를 저장하는 배열로 출력하기 편하게 하기 위해서 위치가 낮은 것부터 저장하였다.

수 n을 2로 나눈 나머지를 저장하여 배열을 저장하고 몫이 0이나 1일때까지 반복한다.