[BOJ] 백준 3943번 : 헤일스톤 수열 (JAVA)

문제

헤일스톤 수열은 다음과 같이 정의한다.

 

• n이 짝수라면, 2로 나눈다.
• n이 홀수라면, 3을 곱한 뒤 1을 더한다.

 

헤일스톤 추측은 임의의 양의 정수 n으로 수열을 시작한다면, 항상 4, 2, 1, 4, 2, 1,...로 끝난다는 추측이다. 이 문제에서는 1이 나오면 수열이 끝난 것으로 처리한다.

 

n이 주어졌을 때, 이 수열에서 가장 큰 값을 찾아 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 다음 줄부터 T개의 줄에는 헤일스톤 수열의 시작값 n이 주어진다. (1 ≤ n ≤ 100,000)

 

 

출력

각각의 테스트 케이스에 대해서, n으로 시작하는 헤일스톤 수열에서 가장 큰 값을 출력한다.

 

 

풀이

단순한 구현 문제였습니다.

 

문제에서 시키는대로 그대로 구현하면 되긴한데, 그렇다면 제가 이 포스팅에서 할 말이 딱히 없겠죠? 저는 여기서 좀 더 최적화해 보겠습니다.

 

헤일스톤 수열의 종료 조건은 N이 1일 때라고 하였습니다. 다시 말하면, N이 2의 거듭제곱일 때 헤일스톤 수열은 종료합니다. 왜냐하면 N이 2의 제곱이라면, 2로 계속 나누다보면 결국 1이 되기 때문이죠.

 

그렇다면, N이 2의 제곱인지 어떻게 알 수 있을까요? 결론부터 말하자면, '(N & (-N) == N' 조건을 만족할 때입니다.

 

N이 2의 제곱 꼴일 때, 이를 비트로 표현하면 1000..000일 것입니다. 이때, -N의 비트를 구하기 위하여 N에 대하여 2의 보수를 취하면 ...11111000..000이 됩니다. 여기서 파란색 글씨를 보면 아시다시피, N에 대하여 2의 보수를 취하면 원래 N의 비트에서 앞에 쭉 1이 붙은 형태가 되는 것을 알 수 있습니다. 따라서, 이 두 개를 &연산을 취하면 N과 동일한 결과값을 얻을 수 있습니다.

 

 

문제에서 주어진 짝수와 홀수일 때의 연산은 그대로 하되, 종료 조건을 1이 아니라 '(N & (-N) == N'로 설정하면 더 빠르게 문제를 해결할 수 있습니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.