BOJ - 창문 닫기 (13909번)

https://www.acmicpc.net/problem/13909

 

처음에 보자마자 감은 안왔는데, 예시를 들어서 일정 범위까지 해보니 규칙을 발견했다.

 

n이 10이라고 해보자

창문을 열고 닫는 과정은 아래와 같다. (처음에는 모두 닫혀져 있음, 0으로 표시 , 열린 창문은 1로 표시)

\  창문         \ 학생 \	1 번 창문	2 번 창문	3 번 창문	4 번 창문	5 번 창문	6 번 창문	7 번 창문	8 번 창문	9 번 창문	10 번 창문
1 번 학생	1	1	1	1	1	1	1	1	1	1
2 번 학생	1	0	1	0	1	0	1	0	1	0
3 번 학생	1	0	0	0	1	1	1	0	0	0
4 번 학생	1	0	0	1	1	1	1	1	0	0
5 번 학생	1	0	0	1	0	1	1	1	0	1
6 번 학생	1	0	0	1	0	0	1	1	0	1
7 번 학생	1	0	0	1	0	0	0	0	0	1
8 번 학생	1	0	0	1	0	0	0	0	0	1
9 번 학생	1	0	0	1	0	0	0	0	1	1
10 번 학생	1	0	0	1	0	0	0	0	1	0

 

10번 까지 결과를 보면 1번, 4번, 9번 만 열려있는 상태를 확인할 수 있다.

그렇다면 1부터 n까지 제곱수를 세어 출력하면 된다는 생각을 해볼 수 있다.

하지만 최악의 경우 n이 21억이 입력될 수 있으므로 반복조건을 신경써야 한다.

내가 제출했고 맞은 코드는 아래와 같다.

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long int ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, cnt = 0;

	cin >> n;
	for (int i = 1; i*i <= n; i++)
	{
		cnt++;
	}
	cout << cnt;
	return 0;
}

반복문의 반복조건을 i*i로 하여 시간 초과가 걸리지 않도록 하였다.