[백준] 1094번: 막대기

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

1094번: 막대기

 

코드

#include <stdio.h>
main() {
	int x, stick = 0;			//x: 입력 받는 수, stick: 막대기 수
	scanf("%d", &x);
	while (x > 0) {
		if (x & 1)
			stick++;
		x >>= 1;
	}
	printf("%d\n", stick);
}

 

설명

 

이 문제는 처음엔 배열로 접근하다가, 반으로 나눈다는 점에 초점을 두고 이진수 비트 연산을 활용해 해결했다.

예를 들어 설명해보겠다.

입력 받는 수가 23이라고 하면, 실행 과정은 다음과 같다.

 

1) 23의 이진수 표현: 0001 0111

2) x & 1이 true이므로 stick++ (현재 stick: 1)

3) x >>= 1: 0000 1011

4) x & 1이 true이므로 stick++ (현재 stick: 2)

5) x >>= 1: 0000 0101

6) x & 1이 true이므로 stick++ (현재 stick: 3)

7) x >>= 1: 0000 0010

8) x & 1이 false이므로 아무것도 하지 않음

9) x >>=1: 0000 0001

10) x & 1이 true이므로 stick++ (현재 stick: 4)

11) x가 0이므로 while문을 종료하고 stick 출력