티스토리 뷰

알고리즘

[Recursive] isTwoPower?

seunggabi 승가비 2018. 9. 6. 22:18

[Recursive] isTwoPower?


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



문제

자연수 N이 주어졌을 때, 2의 제곱수면 1을 아니면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 230)이 주어진다.

출력

N이 2의 제곱수면 1을 아니면 0을 출력하는 프로그램을 작성하시오.



재귀를 이용한 2의 제곱수 찾기.

1 <= N < 2^30 까지 들어올 수 있다.

N을 반으로 줄이면서 푸는 방법을 생각했다.


시간 복잡도: O(LogN)

공간 복잡도: O(LogN) 따로 메모리를 사용하지 않았지만, 함수 호출 스택 갯수이다.


#include <iostream>
using namespace std;

int isTwoPower(int n) {
if(n == 1) return 1;
else if(n % 2 == 1) {
return 0;
}
return isTwoPower(n/2);
}

int main() {
int n;

cin >> n;
cout << isTwoPower(n) << endl;
return 0;
}




댓글
댓글쓰기 폼