백준13909 - 창문 닫기 JS

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

 

해당 문제에는 아래와 같이 접근했다.

최대 입력값이 21억이기 때문에, 반복문으로는 해결할 수는 없으므로 나름의 규칙성이 있을 것이라 판단했다.

따라서 먼저 문제가 요구하는대로 시뮬레이션을 할 수 있는 코드를 먼저 작성해서 적용해보았다.

// 시뮬레이션 코드
function solution(data) {
  const arr = Array.from({length : +data+1}, (_,i)=> [false,i])
  
  for(let i = 1 ; i < +data+1 ; i ++) {
    for(let j = 1 ; j < +data+1 ; j ++) {
      if(j % i === 0) {
        arr[j][0] = !arr[j][0]
      }
    }
  }

  console.log(arr)
}

solution(20)

//
[
  [ false, 0 ],  [ true, 1 ],
  [ false, 2 ],  [ false, 3 ],
  [ true, 4 ],   [ false, 5 ],
  [ false, 6 ],  [ false, 7 ],
  [ false, 8 ],  [ true, 9 ],
  [ false, 10 ], [ false, 11 ],
  [ false, 12 ], [ false, 13 ],
  [ false, 14 ], [ false, 15 ],
  [ true, 16 ],  [ false, 17 ],
  [ false, 18 ], [ false, 19 ],
  [ false, 20 ]
]
//

 

이때 입력값은 임시로 20정도 대입해보았는데,

20 이하의 수 중 자연수의 제곱인 1, 4, 9, 16 만 true값을 가진다는 규칙을 발견했고

즉, 정답은 'n의 제곱근 이하의 정수의 갯수'가 된다.

 

전체 소스 코드

const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim()

function solution(data) {
  // ~~는 Math.floor와 같은 역할을 하는 연산자
  console.log(~~Math.sqrt(data))
}

solution(input)