문제 소개
하나의 숫자 N이 주어졌을 때, 아래 규칙에 따라 이 숫자를 1로 줄이는 데 필요한 총 단계 수를 구하는 것이 목표입니다.
- 규칙 1: 숫자가 2의 거듭제곱이면, 그 절반으로 줄입니다.
- 규칙 2: 2의 거듭제곱이 아니라면, N에서 N보다 작은 가장 가까운 2의 거듭제곱을 뺀 값으로 줄입니다.
먼저 ceil(log2(N))과 floor(log2(N))의 결과가 서로 같은지 비교하여 N이 2의 거듭제곱인지 판별합니다. 두 값이 일치한다면 N은 2의 거듭제곱이므로 N을 절반으로 나누고 연산 횟수를 1 증가시킵니다.
조건이 거짓이라면 두 번째 규칙을 적용합니다. 이때 N보다 작은 가장 가까운 2의 거듭제곱은 다음 과정으로 구할 수 있습니다.
x = floor(log2(N)) → N이 2의 거듭제곱이 아니면 log2(N)은 부동소수점 값을 반환하며, floor()는 이를 N 이하의 가장 큰 정수로 내립니다.
N = N − pow(2, x) → pow(2, x)는 N보다 작은 가장 가까운 2의 거듭제곱을 나타내며, 이를 N에서 빼면 N이 줄어듭니다.
예제로 이해하기
입력: N = 20
출력: 필요한 단계 수 = 3
설명: N = 20
20은 2의 거듭제곱이 아님 → 규칙 2 적용: N = 20 − 16 = 4, count = 1 4는 2의 거듭제곱 → 규칙 1 적용: N = 4 / 2 = 2, count = 2 2는 2의 거듭제곱 → 규칙 1 적용: N = 2 / 2 = 1, count = 3 N이 1이 되었으므로 총 단계 수 = 3
입력: N = 32
출력: 필요한 단계 수 = 5
설명: N = 32
32는 2의 거듭제곱 → 규칙 1 적용: N = 32 / 2 = 16, count = 1 16은 2의 거듭제곱 → 규칙 1 적용: N = 16 / 2 = 8, count = 2 8은 2의 거듭제곱 → 규칙 1 적용: N = 8 / 2 = 4, count = 3 4는 2의 거듭제곱 → 규칙 1 적용: N = 4 / 2 = 2, count = 4 2는 2의 거듭제곱 → 규칙 1 적용: N = 2 / 2 = 1, count = 5 N이 1이 되었으므로 총 단계 수 = 5
프로그램에 사용된 접근 방식
- 정수 값을 저장할 정수형 변수 N을 입력받습니다.
- 함수 stepCount(int n)는 N을 인자로 받아 1로 줄이는 데 필요한 단계 수를 반환합니다.
- 초기 단계 수(count)를 0으로 설정합니다.
- n이 1이 아닌 동안 while 반복문 안에서 n의 값에 따라 규칙 1 또는 규칙 2를 수행합니다.
- n이 2의 거듭제곱이면(ceil(log2(n)) == floor(log2(n))이 참), n을 절반으로 줄이고 count를 1 증가시킵니다.
- 2의 거듭제곱이 아니라면 x = floor(log2(n))을 구한 뒤 n에서 pow(2, x)를 빼고 count를 1 증가시킵니다.
- 반복문이 종료되면 count에는 수행된 총 연산 횟수가 저장됩니다.
- count를 결과값으로 반환합니다.
C++ 구현 예제
#include <iostream>
#include <math.h>
using namespace std;
// N을 1로 줄이는 데 필요한 단계 수를 반환하는 함수
int stepCount(int n){
int count = 0;
while(n != 1){
if(ceil(log2(n)) == floor(log2(n))){ // n이 2의 거듭제곱이면 참
n = n / 2; // n을 절반으로 줄임
count++;
} else {
int x = floor(log2(n)); // 로그값의 내림
n = n - pow(2, x); // 2^x는 n보다 작은 가장 가까운 2의 거듭제곱
count++;
}
}
return count;
}
int main(){
int N = 96;
cout << "N을 1로 줄이는 데 필요한 단계 수: " << stepCount(N);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
N을 1로 줄이는 데 필요한 단계 수: 6
복잡도 분석
매 반복마다 N은 최소 절반 이상으로 줄어듭니다. 2의 거듭제곱인 경우 절반이 되고, 그렇지 않은 경우 N보다 작은 가장 가까운 2의 거듭제곱을 빼면 남는 값은 항상 N/2보다 작기 때문입니다. 따라서 이 알고리즘의 시간 복잡도는 O(log N)이며, 추가 변수만 사용하므로 공간 복잡도는 O(1)입니다.