문제 소개
정수 n이 주어졌을 때, 아래 두 가지 연산을 원하는 만큼 반복 적용하여 n을 0으로 변환해야 하는 문제입니다.
- 연산 1: n의 이진수 표현에서 가장 오른쪽 비트(0번째 비트)를 변경합니다. (0은 1로, 1은 0으로)
- 연산 2: (i-1)번째 비트가 1이고, (i-2)번째부터 0번째까지의 모든 비트가 0일 때, i번째 비트를 변경할 수 있습니다.
최종적으로 구해야 할 것은 n을 0으로 만들기 위해 필요한 최소 연산 횟수입니다.
예제로 이해하기
예를 들어 입력이 n = 6이라면 출력은 4가 됩니다. 6의 이진수 표현은 "110"이며, 다음 순서로 변환할 수 있습니다.
- "110" → "010" (연산 2: 1번째 비트가 1이고 0번째 비트가 0이므로 2번째 비트 변경 가능)
- "010" → "011" (연산 1)
- "011" → "001" (연산 2: 0번째 비트가 0이므로 1번째 비트 변경 가능)
- "001" → "000" (연산 1)
총 4번의 연산으로 6을 0으로 만들 수 있으며, 이보다 적은 횟수로는 불가능합니다.
해결 접근 방법
이 문제의 핵심은 그레이 코드(Gray Code) 변환 원리에 있습니다. n의 이진수 비트를 왼쪽에서 오른쪽으로 순회하면서, 바로 앞에서 처리한 비트 값이 1이면 현재 비트를 뒤집고(XOR), 그렇지 않으면 그대로 두는 방식으로 새로운 비트열을 만듭니다. 이렇게 얻은 비트열을 이진수로 해석한 값이 곧 최소 연산 횟수가 됩니다.
알고리즘을 단계별로 정리하면 다음과 같습니다.
- n을 이진수 비트의 리스트로 변환합니다.
- 결과를 담을 새 리스트 m과 변수 last(초깃값 0)를 준비합니다.
- n의 각 비트 d에 대해 다음을 반복합니다.
- last가 1이면 d를 뒤집습니다. (d = 1 - d)
- last 값을 d로 갱신합니다.
- d를 리스트 m의 끝에 추가합니다.
- m의 모든 요소를 이어 붙여 하나의 이진수 문자열로 만듭니다.
- 그 이진수를 십진수로 변환하여 반환합니다.
파이썬 구현 예제
def solve(n):
n = list(map(int, bin(n)[2:]))
m = []
last = 0
for d in n:
if last == 1:
d = 1 - d
last = d
m.append(d)
m = ''.join(map(str, m))
return int(m, 2)
n = 6
print(solve(n))입력 및 실행 결과
입력: n = 6
출력: 4
복잡도 분석
이 알고리즘은 n의 이진수 자릿수(약 log₂n)에 비례하여 동작하므로 시간 복잡도는 O(log n), 공간 복잡도 역시 O(log n)입니다. 따라서 매우 큰 수가 입력되더라도 효율적으로 최소 연산 횟수를 계산할 수 있습니다.