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

 조금 쉽지만 새로운 유형의 문제를 풀어봤다.

 

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

1094번: 막대기

 

 

문제 해석:

 

 

 문제에서 64cm인 막대에서 시작하여 Xcm인 막대기를 이어붙여 만들어야한다. 이 때, 막대의 합이 Xcm보다 크다면 막대

 

를 절반으로 자른다. 이렇게 자른 막대 중 하나를 제외하고 남은 막대의 길이의 합이 Xcm보다 여전히 크다면 자른 막대 중

 

하나를 버린다. 그리고 이렇게 과정을 반복한다. 예를 들어 X가 23인 막대를 만든다면 64cm에서 나눈 막대는 32cm * 2개

 

인데 막대 하나를 제외해도 23보다 크므로 하나를 버린다. 그러면 32cm 막대 하나만 남는데 이를 또 위와 같은 연산을 통

 

해 16cm막대 2개로 나눈다. 이 때 막대 하나를 제외해도 23보다 작으므로 둘 다 내버려둔다. 그런데, 막대들의 합이 23보

 

다 크므로 길이가 짧은 막대를 또 반으로 나눈다. 그런데 16cm로 같으므로 둘 중 하나만 8cm의 막대 2개로 나눈다. 이러한

 

과정을 반복하여 23cm인 막대를 만드는 것이다. 여기서 문제를 자세히 보면 64라는 수는 2의 6승에 해당하는 수이고, 계속

 

해서 반으로 나누는 과정은 각각의 2의 승수를 만들어 마치 2진수에 해당하도록 만드는 것과 비슷하다. 이런 관점에서 처

 

음 다뤄보는 유형인 비트마스크(Bit Mask)임을 알 수 있다. 컴퓨터사이언스를 조금 공부해본 사람이라면 알겠지만 생

 

소할 수 있다.

 

 

 

알고리즘 해설 및 코드:

 

 

 

코드는 매우 간단하지만 C++의 비트 문법을 다뤄야한다. 위에서 사용된 C++의 비트마스킹 관련 문법을 조금 살펴보자면

 

논리연산자라고도 한다.

 

<<, >>	비트 이동 연산자
|	비트 or 연산자
&	비트 and 연산자
~	비트 not 연산자
^	비트 xor 연산자

 

 

간단하게 살펴보면 비트 이동 연산자는 그 방향대로 비트를 하나씩 이동시키는 연산자이다. 예를 들어 1에서 1 << 2라면

 

0001 에서 1비트를 왼쪽으로 2칸 이동한 0100이 된다.

 

비트 or 연산자는 비교하려는 두 이진수 중 각 자리의 하나라도 1이라면 1로 나타낸다. 예를 들어 0010 | 1100 연산을 실행

 

하면 1110이 연산의 결과값이 된다.

 

비트 & 연산자는 비교하려는 두 이진수에서 두 이진수 모두 각 자리의 1을 나타내면 1로 나타낸다. 예를 들어 0010 & 1111

 

연산을 실행하면 0010의 결과값이 된다.

 

~ 연산자는 not 연산자이다. 말그대로 0이면 1을, 1이면 0을 출력해준다. 예를 들어 ~0110 = 1001이다.

 

^ 연산자는 xor 연산자로 두 이진수에서 둘 중 하나만 1일 경우에만 1을 출력한다. 예를 들어 1010 ^ 0011 의 결과 값은

 

1001 이다.

 

이렇게 살펴봤다면 이제 코드를 살펴볼 차례이다. 문제에서 요구한 조건은 한마디로 몇개의 절반으로 나눠진 막대를 사용

 

해서 만들 수 있는가, 즉 1로 켜져있는 비트의 개수를 구하는 문제이다. 이러한 문제를 해결하기 위해 & 연산자와 << 연산

 

자를 사용했다. 우선 for 문을 돌며 i를 1씩 증가시켜준다. 이 때, i를 하나씩 증가시켜주는 이유는 & 연산을 통해 1비트가 켜

 

져있는지 각 자리마다 확인하려고 한다. 0001에 해당하는 1을 i가 증가하는만큼 << 연산을 통해 left로 shift 해주고 이러한

 

비트와 & 연산을 통해 만약 비트 값이 1이라면 켜져있다는 의미이므로 cnt++를 해주었다. 이렇게 문제를 해결할 수 있었다.

 

 

 

 

간만에 실버 문제를 풀어보았는데 비트 마스킹 문제는 처음이라 낯설었다. 아마 컴공 학부생이라면 어렵지 않게 풀어낼 수

 

있었을텐데 적용해보는 것이 처음이라면 조금 낯설었을 것이다.