티스토리 뷰

공부

[Recursive] isTwoPower?

승가비 2018. 9. 6. 22:18
728x90

[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;
}




728x90

'공부' 카테고리의 다른 글

[DataStructure] bracketComplete? - Stack, Map, String  (0) 2018.09.07
[Recursive] numberPower?  (0) 2018.09.06
[DB] 트랜잭션(작성중)  (0) 2018.08.27
[OS] Process & Thread  (0) 2018.08.20
[DB] 정규화  (0) 2018.08.16
댓글