[백준 1094번 C/C++] 막대기

 

[백준 1094번 C/C++] 막대기

 

 

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

1094번: 막대기

---

 

해결방안

 

비트

수학

 

주어진 수 x를 2진수로 표현했을 때의 1의 개수가 우리가 구하고자 하는 막대의 개수와 같다.

 

---

 

정답코드

 

#include <iostream>
using namespace std;

int x; // 입력 받을 수
int cnt; // 막대의 개수

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> x;

	// 비트 연산을 이용해 막대기의 개수를 센다
	for(int i = 0; i <= 6; i++) // 64는 2의 6제곱이므로 i는 0부터 6까지
	{
		// 이 연산 결과가 0이 아니면, 해당 비트는 1이므로 막대기가 존재하는 것이고, 그 때마다 cnt를 1씩 증가.
		if (x & (1 << i)) { // x의 i번째 비트가 1이면
			cnt++; // 막대기의 개수를 증가
		}
	}

	cout << cnt;

	return 0;
}

 

 

 ( 1 << i )

• 1을 왼쪽으로 i번 시프트하는 연산이다. 2의 i 제곱에 해당하는 값을 비트로 표현한 것이다
• ex. i가 2일 경우 (1 << i)는 4에 해당하는 100(2진수)을 나타낸다.

 

x & ( 1 << i )

• x와 (1 << i)의 비트 단위 AND 연산을 수행한다.
• 이 연산은 x의 i번째 비트가 1인지 0인지를 판별한다.
• 즉, if (x & (1 << i))는 "x의 i번째 비트가 1이면" 이라는 조건을 의미한다.
• 이 조건이 참이면, cnt++를 통해 막대기의 개수를 증가시킨다.

 

비트 연산을 이용하면, 각각의 막대기를 표현하는 비트가 1인지 0인지를 빠르게 판별하고, 막대기의 개수를 세는 것이 가능합하다.

 

 

테스트 케이스 

• x = 23일 때, 10111(2진수)
  • 64cm → 32cm  →  16cm cnt++  →  8cm  →  4cm cnt++  →  2cm cnt++  →  1cm cnt++ 
• x = 32일 때, 100000(2진수)
  • 64cm → 32cm cnt++
• x = 64일 때, 1000000(2진수)
  • 64cm cnt++
• x = 48일 때, 110000(2진수)
  • 64cm → 32cm cnt++  → 16cm cnt++ 

 

---