- boj 1799 ac, 플5
가장 중요한 아이디어는 비숍이 놓인 칸의 색깔이 다르면 서로에게 영향을 주지 못한다는 것이다. 이를 통해 시간복잡도를 N^2의 1/4 만큼으로 줄일 수 있다.
- boj 11689 ac, 골1
gcd(최대공약수)가 1인, 즉 자연수 n에 대해 n 이하인 서로소의 개수를 구하는 문제이다. 오일러 피 함수의 대표격인 문제로 n의 소인수만 알고 있으면 풀리는데, 나는 이미 4149(큰 수 소인수분해)를 풀었기 때문에 이 코드를 그대로 가져와 조금만 수정해 ac를 받았다.
- boj 13926 ac, 다5
바로 위 문제의 hard 버전이다. n 제한이 크게 늘었는데, 소인수 분해를 할 때 폴라드 로 알고리즘을 사용하라는 의도같다.
js는 큰 수를 처리하려면 BigInt 타입을 사용해야하는데, 이것 때문에 진짜 많이 wa를 받았다. 분명 큰 수를 처리하기 위한 타입인데, 왜 혼자서 정수 반올림을 하고 처리하는가..
TypeError: Cannot convert a BigInt value to a number
이 오류도 많이 받았다. 내용 그대로 BigInt와 일반 Number 타입을 혼용해서 쓸 수 없다는 뜻인데, 문제는 아무리 찾아도 그런곳이 없다는 것이였다. 약 40분간 삽질해서 결국 원인을 찾아냈는데, sort 함수는 BigInt를 정렬시킬 수 없단다. 까짓거 좀 해주지..
sort 함수를 사용할때만 Number 타입으로 변환해서 제출했더니 결국 ac를 받았다.
