[백준JS] 13909. 창문 닫기

안녕하세요. 박기린 입니다.

백준 13909번 창문 닫기 문제를 풀어봅시다.

 

 

문제 링크

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

 

---

문제 해석

const fs = require("fs");
const input = +fs.readFileSync("/dev/stdin").toString().trim();
const windows = Array(input + 1).fill(false);


const execute = (n) => {
    for (let i = 1; n * i <= input; i++) {
        windows[n * i] ? windows[n * i] = false : windows[n * i] = true;
    }
}


for (let i = 1; i <= input; i++) {
    execute(i);
}

windows.shift();

console.log(windows.filter(e => e === true).length);

위 코드처럼 for 문을 이용해서 일일이 문을 열고 닫는 코드를 구현했더니 '메모리 초과'가 뜨면서 틀렸습니다.

 

 

그러던 중, 입력값으로 1부터 25까지 하나씩 넣고 결과값을 출력해보니 어떠한 규칙을 발견했습니다.

규칙 찾기
1 ~ 3 : 1
4 ~ 8 : 2
9 ~ 15 : 3
16 ~24 : 4
25 : 5

-> 제곱근의 정수 부분

입력값의 제곱근의 정수 부분이 답이었습니다.

 

 

원리는 무엇일까요?

n번째 창문이 열려 있으려면, 그 창문을 열고 닫은 횟수가 홀수번이어야 합니다.

그럴려면 n의 약수의 갯수가 3개여야 합니다.

n = 4일 경우,
1번째 사람, 2번째 사람, 4번째 사람이 4번째 문을 열고 닫고 연다.

n = 9일 경우,
1번째 사람, 3번째 사람, 9번째 사람이 9번째 문을 열고 닫고 연다.

즉, 약수의 갯수가 3인 n번째 창문이 열려 있습니다.

그리고 약수의 갯수가 3이려면 제곱수여야 합니다.

 

따라서 1, 4, 9, 16, 25 .... 를 기점으로 열린 창문의 갯수가 하나씩 증가합니다.

 

 

---

정답 코드

const fs = require("fs");
const input = +fs.readFileSync("/dev/stdin").toString().trim();
console.log(Math.floor(Math.sqrt(input)));

 

 

---

정답 코드 풀이

Math.floor(Math.sqrt(input));

Math.sqrt()는 number의 제곱근을 구하고, Math.floor()는 number의 소수 부분을 제거하여 정수부분만 남깁니다.

이 두 함수를 이용해서 제곱근의 정수부분을 구하고, 출력합니다.