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

백준 온라인 저지(BOJ) 13909번 창문 닫기

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

13909번: 창문 닫기

* 사용언어 : C언어, C++

 

1. 문제

N개의 창문, N명의 사람이 있는 방

각 사람은 해당되는 숫자의 배수의 창문을 열려있으면 닫고, 닫혀있으면 열음

N번째 사람까지 진행한 후 열려 있는 창문의 개수를 출력

 

2. 풀이

에라토스테네스의 체(혹은 소수)와 관련된 문제인가 싶어서 고민해봤는데 관련이 없다는 것을 알게 됐습니다.

배수 or 약수와 관련이 있을 것 같긴 했는데 감이 안와서 1부터 직접 결과를 작성해보았습니다.

 

column : 창문, row : 사람 (row를 1씩 늘리면서 0↔1 변경)

 

해당 작업을 16까지 해본 후에야 완전 제곱수만 1이 된다는 것을 알 수 있었습니다.

 

결과를 놓고 생각해보니 각 숫자에 대해서 자신의 약수들이 해당 숫자를 지나가면서 0 ↔ 1 변경을 하므로

약수의 개수가 홀수인 숫자만 1이 된다는 것도 알 수 있었습니다.

(예를 들어 8은 약수가 4개(1, 2, 4, 8)로 짝수이고, 완전 제곱수인 9는 약수가 3개(1, 3, 9)로 홀수)

 

 

입력 N에 대해서 N 이하의 완전 제곱수 개수를 출력하면 되기 때문에

단순하게 루트를 씌운 후 내림(int 형변환)을 해서 출력해주었습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
13909_창문 닫기
1124KB	0ms
*/
#include <cstdio>
#include <math.h>

int n;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &n);
	printf("%d\n", (int)sqrt(n));
	return 0;
}