[백준 BOJ] 3460번 이진수 (C++/cpp)

문제 설명

https://www.acmicpc.net/problem/3460

 

 

접근 방법 - 진법 변환 기초 연산 문제

백준의 3460번 문제는 진법 변환에 있어 기초적인 연산 문제이다.

해당 문제는, 입력으로 주어지는 숫자를 2진법으로 변환할 때 1이 표시되는 위치들을 오름차순으로 출력해야 하는 문제이다.

이때, 문제 상에서 최하위 비트의 위치는 0이라는 점이 명시되어 있으니 함께 참고하면 된다.

 

문제 해결에 앞서, 문제의 본질인 10진법 -> 2진법 변환 방법부터 꿰는 것이 좋을 듯하다.

예제 입출력으로 제시된 13을 예시로 들자면, 위와 같이 2진법 변환을 진행할 수 있다.

더 이상 나눌 수 없을 때까지 2진법의 2로 나누기를 연속으로 진행하고, 마지막에 남은 몫과 나머지들을 역순으로 나열하면 된다.

여기서 그림을 잘 보면, 첫 번째 나눗셈의 나머지 값은 문제에서 설명한 최하위 비트의 값을 의미한다는 점을 알 수 있다.

그리고 그 이후로는 첫 번째 비트, 두 번째 비트... 식으로 나열이 된다는 점을 확인할 수 있다.

 

이러한 점을 이용하여, 필자는 2로 나누어가며 그때마다 나눗셈 나머지가 1인지를 판별하고 답을 출력하는 식으로 하여 문제를 해결해 보았다.

자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 테스트 케이스의 수(n)를 입력받는다.

 

2) n의 크기만큼, 반복문을 수행하여 아래의 연산을 취한다.

- 연산을 수행할 숫자(num)를 입력받는다.

- num에 대한 2진법 변환 연산을 진행하면서, 문제에서 요구하는 정답을 순차적으로 출력해 나간다.

(1) 다른 반복문을 추가로 만들어, 2진법 변환 연산을 준비한다. 
(제어 변수 j로 비트 위치를 파악하고자 한다. 초기값을 0으로 설정하고 한 바퀴 순회할 때마다 1씩 증가시킨다.)
(num을 2로 계속 나누어나갈 예정이기 때문에, 더 이상 나누지 못하게 될 때 해당 반복문을 종료할 예정이다.)
(2) num을 2로 나누어보았을 때 나머지로 1이 나타난다면, 2진법의 현재 위치에서는 1로 표시됨을 의미한다.
따라서 이 경우에는, 현재 비트 위치를 의미하는 j를 출력하도록 한다.
(3) (2)가 완료되었다면, 현재 num을 2로 나누어 몫만 남겨두고 위 연산을 반복하도록 한다.

 

3) 2)에서 정답 출력이 완료되었다면, 실행을 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 3460번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;
    
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;

		for (int j = 0; num > 0; j++) {
			if (num % 2 == 1) {
				cout << j << " ";
			}
			num /= 2;
		}
	}
}

 

제출 결과

(2022.07.21 백준 3460번 문제 제출 결과)