반응형
백준 13909번 창문 닫기 (javascript, node.js)
문제
- 백준 13909번 창문 닫기 보러 가기
- 서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.
- 예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,
13909번: 창문 닫기
서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 2번째 사람은 2의 배수 번째
www.acmicpc.net
- 1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
- 2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
- 3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)
- 결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.
입력
- 첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.
출력
- 마지막에 열려 있는 창문의 개수를 출력한다.
예제입력 1
3
예제출력 1
1
예제입력 2
24
예제출력 2
4
문제풀이
- 처음에는 에라토스테네스의 체로 풀려했지만 잘 안되었다.
- 문제를 보고 풀기에는 어려웠던 문제
- 문제를 보면 결국 패턴이 있는데 1,4,9,16,25 이렇게 창문이 열려 있는 수가 증가한다.
- 위 수가 제곱수이기에 제곱수를 구하는 프로그램을 작성하면 됨
// 13909번 창문 닫기
// 처음에는 모든 창문이 닫혀 있다
// 1 부터 n 까지 해당하는 숫자의 배수일때 문을 열고 닫는다
// 1 일때 모두 배수이므로 n번까지 창문을 연다.
// 2 일때 2의 배수의 창문을 닫는다(닫혀있으면 열기).
// 3 일때 3의 배수의 창문을 닫는다(닫혀있으면 열기).
// n=1 일때 1 창문이 한개 열려있고
// n=2 일때 1,0, 첫번째는 열리고 두번째 닫힘
// n=3 일때 1,0,0 첫번째는 열리고 2,3번째 닫힘
// n=4 일때 1,0,0,1 첫번째 열리고 마지막 열림
// .... n=9일때 1,0,0,1,0,0,0,0,1 기존이랑 같고 마지막 열림
// 결국 n이 1,4,9,16,25 제곱수 일때 문이 창문이 하나씩 증가하기 때문에
// 제곱수를 구해주면됨
const fs = require("fs");
const file = process.platform === "linux" ? "dev/stdin" : "./text.txt";
const input = fs.readFileSync(file).toString().trim();
const n = parseInt(input);
var result = 0;
// 제곱수를 구하는식
for (i = 1; i * i <= n; i++) {
result++;
}
console.log(result);
// Math.sqrt()로 제곱근을 구하고 Math.floor로 소수점 정리해줘도됨
// console.log(Math.floor(Math.sqrt(n)));
'Algorithm_javascript > 15. 약수, 배수와소수2' 카테고리의 다른 글
| # 백준 17103번 골드바흐 파티션 (javascript, node.js) (0) | 2023.07.26 |
|---|---|
| # 백준 4948번 베르트랑 공준 (javascript, node.js) (0) | 2023.07.24 |
| # 백준 4134번 다음 소수 (javascript, node.js) (0) | 2023.07.22 |
| 백준 2485번 가로수 (javascrit, node.js, 자바스크립트, 노드) (2) | 2023.05.25 |
| 백준 1735번 분수합 (javascript, node.js) (0) | 2023.05.24 |