[C#]백준 1094 막대기 - Hide

반응형

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

문제 요약

주어진 수 X는 64,32,16,8,4,2,1 중에 몇 개를 조합해서 만들 수 있는지 출력하기

 

 

풀이 1

int c = 0, n = 64, x = int.Parse(Console.ReadLine());

for (; x > 0; n /= 2) if (n <= x) { x -= n; c++; }
Console.Write(c);

변수는 각각 개수를 세줄 c, 64를 계속 반으로 쪼개줄 n, 주어진 수 x

 

for문은 (n이 0보다 클 때까지 반복; n을 2로 나눠주기)

만약 x가 n이하라면 n에서 x를 빼주고 c++ 해준다.

 

n이 0이 되면 반복문을 빠져나가 c를 출력한다.

 

 

---

그런데 사실 이 문제는 비트 관련해서 풀 수 있다.

 

예제를 이진수로 표현하면 다음과 같다.

각각의 수를 이진수로 표현했을 때 1의 위치를 [64,32,16,8,4,2,1]에 대입해 보면

로 맞아떨어진다.

 

그러므로 입력을 바로 이진수로 변환해서 1의 개수를 세면 반복을 돌리지 않아도 되고 변수도 필요 없다!

 

 

 

참고

 

십진수를 이진수로 변환하는 법 => Convert.ToString(int형 변수, 2)

문자열에서 원하는 문자의 개수 세는 법 => 문자열.Count(x => x== '문자')

(파이썬과 자바에서는 bitcount라는 변수를 통해 바로 이진수에서 1의 개수를 세준다. C#에는 없는 듯)

 

 

 

풀이 2

Console.Write(Convert.ToString(int.Parse(Console.ReadLine()),2).Count(x=>x=='1'));

 

단 한 줄로 끝내버리기

---

비트는 진짜 사기템이다... 근데 나는 이진수 잘 모름 ㅎ