[백준 / BOJ] 13909번 창문 닫기 (Javascript / Node js)

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

13909번: 창문 닫기

 

문제 해석

문제는 입력받은 N개의 창문을 1부터 N까지 1의 배수에 사람들이 서있고, 2의 배수에 또 다른 사람들이 서있고, 3,, N의 배수에 사람들이 서있어서 1번째부터 N번째의 창문까지 각각의 창문이 그 창문에 서있는 사람의 수만큼 창문이 열리고 닫히고, 1번째부터 N번째 창문까지 열려있는 창문의 개수를 구하는 문제이다. 

 

N의 범위가 21억까지여서 처음에는 도통 감이 안잡혔는데, 규칙을 찾기 위해 메모장에 수를 나열하고 보니 생각보다 너무 쉽게 풀려서 웃음이 나왔다.

 

문제에 나와있듯이 창문이 열려있음을 1, 닫혀있음을 0으로 표현했다. 그리고 각 1부터 n의 배수들에 원래 있던 값을 1이면 0으로 0이면 1로 반전시키는 연산을 반복했다.

 

 

그 결과 최종적으로 마지막 결과가 1로 남아있는 수들(4, 9)에서 규칙을 찾을 수 있었다.

 

바로 자연수의 제곱수라는 것이다. 그래서 제곱수인 것과 마지막이 1로 끝나는 것이 어떤 연관이 있을지 생각해봤고,

제곱수인 경우 약수 중 하나는 제곱수의 제곱근이니 약수의 총 개수가 홀수일 수 밖에 없다는 것을 깨달았다. ex) 4 => (1, 2, 4) / 9 => (1, 3, 9).

 

때문에 제곱근이 아닌 것들은 약수의 개수가 짝수이니 0으로, 제곱수들은 홀수이니 마지막에 1로 반전시켜 창문이 열려있는 상태로 남게 된 것이다. 이를 토대로 로직을 구현하면 N의 최대범위인 21억을 입력 받아도 21억의 제곱근으로 반복문의 범위를 줄여버릴 수 있었다.

 

전체 코드

 

const fs = require("fs");

const input = fs.readFileSync("../input.txt").toString().trim();

const N = Number(input);

let cnt = 0;

for(let i=1; i*i <= N; i++){

    cnt++;

}

console.log(cnt);