문제
양의 정수 X가 주어질 때, 1부터 시작하는 홀수 수열에서 합이 X 이하인 최대 항의 수를 구하라.
입력
여러 양의 정수 X가 주어지며, 0이면 종료한다.
출력
각 X에 대해 (X + 1) / 2를 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 0 | 4 |
풀이
수학 공식으로 직접 답을 계산한다.
- 결과는
(X + 1) / 2이다 - 정수 나눗셈의 올림 효과를
(X + 1) / 2로 구현한다
핵심 아이디어: 공식 (X + 1) / 2로 O(1)에 답을 구할 수 있다.
코드
#include <iostream>
using namespace std;
int main(void)
{
cin.tie(0);
ios::sync_with_stdio(0);
long long int x;
while (1)
{
cin >> x;
if (!x)
break;
cout << (x + 1) / 2 << '\n';
}
}복잡도
- 시간: O(T)
- 공간: O(1)