2018. 9. 24. 21:12, 알고리즘/BOJ
https://www.acmicpc.net/problem/16136
f(A) = A의 약수의 갯수라고 할 때, f(A)는 2*sqrt(A) 이하이므로 대충 5-6번 정도만 연산을 하고 나면 2가 될 것입니다. (물론 A가 1이면 f(A)는 1이고요.) 그러니 1번째 작업의 경우는 각 수에 대해서 대충 5번 정도만 이루어지고 나면 더 이상 할 필요가 없는 작업이 됩니다. 저는 segment tree 2개를 두어, 첫 번째 segment tree는 일반적인 구간 합을 처리하는 segment tree이고 두 번째 segment tree는 특정 수가 2 이하인지를 확인하는 segment tree로 두어 1번 쿼리가 들어왔을 때 현재 확인한 node의 st부터 en까지가 전부 2 이하일 경우 더이상 따라들어가지 않고 return, 또 현재 확인한 node의 st부터 en까지가 전부 2 초과일 경우 연산을 진행하는 방식으로 처리했습니다.
다른 사람의 코드를 보니 구간 합을 처리하는 segment tree 1개에 union find로 해결을 한 경우도 있었습니다.
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 10677번: It's All About the Base (0) | 2018.09.25 |
---|---|
[BOJ] 1591번: 수열 복원 (0) | 2018.09.25 |
[BOJ] 1062번: 가르침 (0) | 2018.09.24 |
[BOJ] 16161번: 가장 긴 증가하는 팰린드롬 부분수열 (0) | 2018.09.23 |
[BOJ] 15927번: 회문은 회문아니야!! (0) | 2018.09.23 |
[BOJ] 1557번: 제곱ㄴㄴ (2) | 2018.09.23 |
Comments