백준 30704

문제

풀이

둘레의 규칙성을 파악하면 풀 수 있는 문제다.

도형 둘레의 최솟값인 것을 인지하면 된다.

한개인 경우 4, 두개인 경우 6, 세개인 경우 8, 네개인 경우 8, 다섯개인 경우 10 이렇게 쭉 써내려 가면

4 6  8 8 10 10  12 12 12 14 14 14  16 16 16 16 ~~~ 이라는 규칙성을 발견할 수 있다.

이를 개수로 치환하여 1 1 2 2 3 3 4 4 5 5 6 6 ~ 으로 특정한 둘레의 개수의 규칙성으로 치환할 수 있다.

cnt 가 1씩 증가하는 경우가 2개씩 중복된 숫자가 나오는 경우로 생각해서 누적합을 구하면 어느 경우에 해당하는 수가 몇개의 직사각형의 최소 둘레인지 알 수 있다.

이 규칙헤 대한 개수를 누적합으로 치환하여 이분탐색으로 해결했다. 

 

다른 풀이를 보니 단순 수식으로 풀 수 있는거 같다.

 

#include <iostream>
using namespace std;
long long T, arr[1000001];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int chk = 0, cnt = 1;
    for(int i=1; i<=63245; i++) {
        arr[i] = cnt + arr[i-1];
        chk += 1;
        if(chk == 2) {
            chk = 0; cnt += 1;
        }
    }
    
    cin>>T;
    while(T--) {
        int N; cin>>N;
        int lo = 0, hi = 63245;
        while(lo+1 < hi) {
            int mid = (lo+hi)/2;
            if(arr[mid] >= N) hi = mid;
            else lo = mid;
        }
        cout<<4+lo*2<<"\n";
    }
}