Codeforces #1419B Stairs

문제

https://codeforces.com/problemset/problem/1419/B

걸린 시간

01 : 46 : 57 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        ll x;
        cin >> x;
        ll stairs = 1;    
        int ans = 0;
        while(true){
            ll cells = stairs*(stairs+1)/2;
            if(x-cells < 0)
                break;
            x -= cells;
            stairs += pow(2, ans+1);
            ans++;
        }
        cout << ans << "\n";
    }
    return 0;
}

nice 하게 만들 수 있는 조건의 설명을 제대로 읽지 않고 그림과 입력 예제의 설명으로 이해하려 했던 것이 실수였다.

n개의 층을 n개의 서로 다른 정사각형으로 채울 수 있는 경우는 2ⁿ-1 층이라는 점을 찾아내면 쉽게 풀이할 수 있다.