7/25 연습

2017. 7. 26. 11:00알고리즘 문풀/BOJ 연습

1. 이상한 수열 (OJUZ #10)


http://icpc.me/11917

http://oj.uz/problem/view/OJUZ10_bizarre


풀이 :


oj.uz에서 처음 봤을 때 아무 생각 없이 62점을 받고 넘겼던 문제다. 100점 풀이 생각 못한 뚝배기를 매우 쳐라


\(M\)이 비상식적으로 크므로, \(B_i\)의 값을 거의 닫힌 꼴로 구할 수 있을 것이라는 생각을 해야 한다. \(S\)를 오름차순으로 정렬한 뒤, \(B_{n+1}\)의 값 (\(S_1, S_2, \cdots S_n\) 중 서로 다른 수의 개수)이 어떤 \((S_i,S_{i+1}]\)에 있게 되면 이 값은 \(S_{i+1}\)로 수렴하고(편의상 \(S_{n+1} = \infty\)라 두자), 그 전까지는 값이 1씩 증가하게 됨을 어렵지 않게 보일 수 있다.


Time Complexity : \(O(N lgN)\)



데이터를 다 썼는데 어제 핫스팟 틀어줄 천사를 찾지 못해서 한 놈밖에 못 풀었스ㅂ니 ㄷ.... 오늘 빡세게 해야지. 

'알고리즘 문풀 > BOJ 연습' 카테고리의 다른 글

7/30 ~ 7/31 연습  (0) 2017.08.01
7/29 연습  (0) 2017.07.30
7/27~7/28 연습  (0) 2017.07.29
7/26 연습  (0) 2017.07.27
7/25 연습  (0) 2017.07.26
7/24 연습  (0) 2017.07.25