문제 소개
정수형 변수 Number가 입력으로 주어집니다. 1부터 Number까지의 범위에 속한 값들이 정렬된 순서로 담긴 배열을 생각해 보겠습니다. 이 배열에 대해 매 단계마다 홀수 번째 위치에 있는 요소들을 제거하는 연산을 수행합니다. 목표는 이 연산을 배열에 단 하나의 요소만 남을 때까지 반복한 뒤, 마지막에 남은 요소를 출력하는 것입니다.
참고: 요소의 위치는 인덱스 0에 해당하는 요소를 1번째 위치로 간주하며, 이후 순차적으로 계산합니다.
배열 요소 개수별 테스트 케이스
입력 Number=1, 출력 = 1
입력 Number=2, 출력 = 2
입력 Number=3, 출력 = 2
입력 Number=4, 출력 = 4
입력 Number=5, 출력 = 4
입력 Number=6, 출력 = 4
입력 Number=7, 출력 = 4
......
입력 Number=12, 출력 = 8
입력 Number=20, 출력 = 16
위 관찰 결과를 바탕으로, 2i 부터 2i+1-1 사이 범위의 숫자에 대한 출력은 항상 2i라는 규칙을 도출할 수 있습니다. 즉, 마지막에 남는 요소는 입력값 이하의 가장 큰 2의 거듭제곱입니다.
예시
입력 − Number=7
출력 − 감소 연산 후 남은 단일 요소 : 4
설명 − 첫 번째 요소는 1번째 위치에 있으며, 이후 순차적으로 위치가 결정됩니다.
초기 배열은 [ 1 2 3 4 5 6 7 ] 입니다.
1차 연산 후: [ 2 4 6 ]
2차 연산 후: [ 4 ]
입력 − Number=18
출력 − 감소 연산 후 남은 단일 요소 : 16
설명 − 첫 번째 요소는 1번째 위치에 있으며, 이후 순차적으로 위치가 결정됩니다.
초기 배열은 [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ] 입니다.
1차 연산 후: [ 2 4 6 8 10 12 14 16 18]
2차 연산 후: [ 2 8 12 16 ]
3차 연산 후: [ 8 16 ]
4차 연산 후: [ 16 ]
접근 방식
아래 프로그램에서는 위에서 확인한 공식을 기반으로 while 루프를 사용해 최종 결과를 계산합니다. 초기값을 2로 설정한 뒤, result * 2가 입력값 이하인 동안 반복하면서 매번 result를 두 배씩 늘려갑니다.
입력 변수 Number를 받습니다.
getsingleElement(long num) 함수가 입력 숫자를 전달받아 위 공식에 따라 결과를 계산합니다.
변수 result를 선언합니다.
result를 2로 초기화합니다.
while 루프를 사용해 result * 2 <= num 조건이 만족되는 동안 순회합니다.
루프 내부에서 result를 두 배로 만듭니다.
while 루프가 종료되는 순간 원하는 값을 얻게 됩니다.
result를 반환합니다.
main 함수에서 결과를 출력합니다.
구현 예시
#include<bits/stdc++.h>
using namespace std;
long getsingleElement(long num){
long result;
result=2;
while(result*2 <= num){
result=result*2;
}
return result;
}
int main(){
int Number = 20;
cout<<"The single element after reduction operation is : "<<getsingleElement(Number) ;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
The single element after reduction operation is : 16