[BOJ] 9537번: Magical GCD

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


수열에서의 GCD는 매우 중요한 성질이 있는데, 값의 변화가 많아봐야 log2(MAX)만큼 일어난다는 것입니다. 예를 들어 문제의 예시인 30 60 20 20 20의 경우, (30) -> 30, (30 60) -> 30, (30 60 20) -> 10, ... 을 볼 때 값의 변화가 한 번 일어났습니다. 왜냐하면 값이 변할 때 적어도 2로 나누어져야하기 때문입니다. 같은 값이 여럿 있을 때에는 가장 길이가 길게 하는, 즉 제일 왼쪽의 것만 계속 들고가면 됩니다. 이제 진행하면서 값이 변화하는 지점만 들고가면, $O(Nlg(10^12))$에 해결이 가능합니다.


예를 들어 30 60 20 20 20의 경우,

30을 보고난 후 (30, 0)

60을 보고난 후(30, 0), (60, 1)

20을 보고난 후(10, 0), (20, 2)

20을 보고난 후(10, 0), (20, 2)

20을 보고난 후(10, 0), (20, 2)


을 들고갑니다. 저는 그냥 vector를 N개 잡아 해결했는데 map을 가지고 해결한 코드도 볼 수 있었습니다.


https://github.com/blisstoner/BOJ/blob/master/9537.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 13509번: 가장 가까운 두 점 2  (0) 2018.07.30
[BOJ] 1205번: 등수 구하기  (0) 2018.07.30
[BOJ] 10256번: Mutation  (0) 2018.07.28
[BOJ] 1605번: 반복 부분문자열  (0) 2018.07.27
[BOJ] 15902번: Split and Merge  (0) 2018.07.27
[BOJ] 15903번: 카드 합체 놀이  (0) 2018.07.27
  Comments