[Baekjoon]15736번 청기 백기 - Javascript

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

15736번: 청기 백기

문제

소프트웨어융합대학 학생회에서 주최한 소융체전에서 청기 백기 뒤집기 게임이 한창이다. 소프트웨어학부, ICT융합학부가 번갈아가면서 게임을 진행하는 중이다. 게임의 규칙은 간단하다. 게임을 진행할 차례인 학부에서 출전한 선수들 N명이 존재한다. 학생들의 앞 탁자에는 N개의 깃발이 청색이 위로 백색이 아래로 보이도록 놓여있다. 이때 출전한 선수 중 첫 번째 선수는 N개의 깃발 중 1의 배수에 해당하는 번호의 깃발을 뒤집어 놓는다. 다음 두 번째 선수는 N개의 깃발 중 2의 배수에 해당하는 번호의 깃발을 뒤집어 놓는다. i 번째 선수는 i의 배수에 해당하는 번호의 깃발을 뒤집고, N 번째 선수까지 진행하면 끝이 난다. 그렇다면 이 게임에서 N 명의 선수가 참가하고 N개의 깃발이 존재할 때, N 번째 선수까지 진행하여 완료된 상태에서 백색이 위로 놓여있는 깃발의 수가 몇 개인지 알아보자.

입력

첫 번째 줄에 출전한 학생의 수이자, 깃발의 개수인 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.

출력

첫 번째 줄에 N 번째 선수까지 진행한 후의 상태의 깃발 중 백색이 위로 놓여있는 깃발의 수를 출력한다.

예제 입력 1 복사

3

예제 출력 1 복사

1

예제 입력 2 복사

24

예제 출력 2 복사

4

 

문제풀이(1)

모든 깃발이 위가 청색일 때, N명의 사람이 i배수 만큼 뒤집게된다. 이때, 해당 번호의 약수가 홀수 인것은 백기가 된다.
백기의 개수를 구하는 문제이기 때문에 해당 번호의 약수가 홀수인 것을 찾으면 될 것이다.
1 = 1번 = 백기, 2 = 2번 = 청기, 3 = 2번 = 청기, 4 = 3번 = 백기 ...
루트 i 가 정수일 때, 약수가 홀수로 나오게 된다.
시간제한이 1초이고, N은 최대 21억 번이기 때문에 일반적인 반복문을 순회할 경우 21초 걸리게된다.
그렇기 때문에 루트 i가 N보다 작을 경우를 카운트 해주면 된다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const N = Number(require("fs").readFileSync(filePath).toString().trim());

// 1 = 백기, 2 = 청기기 때문에 초기 값을 1로 둔다.
let answer = 1;

for (let i = 2; i * i <= N; i++) {
  answer++;
}

console.log(answer);