문제
공의 현재 크기 x와 목표 크기 w가 주어진다. 매 단계마다 공의 크기를 2배로 늘릴 수 있을 때, x가 w 이상이 되기까지 필요한 최소 단계 수를 구한다. T개의 테스트 케이스가 주어진다.
입력
첫 번째 줄에 테스트 케이스 수 T가 주어진다. 이후 T개의 줄에 각각 정수 x와 w가 주어진다.
출력
각 테스트 케이스에 대해 필요한 단계 수를 한 줄씩 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 1 8 3 7 5 5 | 3 2 0 |
풀이
while 루프로 x가 w 이상이 될 때까지 2배 연산을 반복하며 횟수를 센다.
- T개의 테스트 케이스를 순서대로 처리한다.
- 각 케이스마다 카운터
ans를 0으로 초기화한다. x < w인 동안x *= 2,ans++를 반복한다.ans를 출력한다.
핵심 아이디어: 크기가 매번 2배씩 늘어나므로 최대 반복 횟수는 log2(w/x)에 비례한다. 입력 범위가 작다면 단순 시뮬레이션으로 충분하며, 수학적으로는 ceil(log2(w/x))로 계산할 수도 있으나 시뮬레이션이 더 직관적이다.
코드
#include <iostream>
#include <algorithm>
using namespace std;
int t, x, w, ans;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t--)
{
ans = 0;
cin >> x >> w;
while (x < w)
{
x *= 2;
ans++;
}
cout << ans << '\n';
}
}복잡도
- 시간: O(T * log(w/x)) — 각 테스트 케이스마다 2배씩 증가하므로 로그 횟수만큼 반복
- 공간: O(1) — 추가 자료구조 없음