[백준 13909번] 창문 닫기 (C++)

문제링크 : https://www.acmicpc.net/problem/13909

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

int N;
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;

    cout << sqrt(N);

    return 0;
}

 

직접 경우의 수를 체크해보면 규칙이 보인다.

n=3 -> 1
1 1 1
1 0 1
1 0 0

n=4 -> 2
1 1 1 1
1 0 1 0
1 0 0 0
1 0 0 1

n=5 -> 2
1 1 1 1 1
1 0 1 0 1
1 0 0 0 1
1 0 0 1 1
1 0 0 1 0

n=6 -> 2
1 1 1 1 1 1
1 0 1 0 1 0
1 0 0 0 1 1
1 0 0 1 1 1
1 0 0 1 0 1
1 0 0 1 0 0

n=7 -> 2
1 1 1 1 1 1 1 
1 0 1 0 1 0 1
1 0 0 0 1 1 1
1 0 0 1 1 1 1
1 0 0 1 0 1 1
1 0 0 1 0 0 1
1 0 0 1 0 0 0

n=8 -> 2
1 1 1 1 1 1 1 1
1 0 1 0 1 0 1 0
1 0 0 0 1 1 1 0
1 0 0 1 1 1 1 1
1 0 0 1 0 1 1 1
1 0 0 1 0 0 1 1
1 0 0 1 0 0 0 1
1 0 0 1 0 0 0 0


n=9 -> 3
1 1 1 1 1 1 1 1 1
1 0 1 0 1 0 1 0 1
1 0 0 0 1 1 1 0 0
1 0 0 1 1 1 1 1 0
1 0 0 1 0 1 1 1 0
1 0 0 1 0 0 1 1 0
1 0 0 1 0 0 0 1 0
1 0 0 1 0 0 0 0 0
1 0 0 1 0 0 0 0 1

 

이처럼 n의 제곱근이 정답이 되는 것을 볼 수 있다.