2018/06/26 썸네일형 리스트형 BOJ)15589 Lifeguards (Silver) 문제: icpc.me/15589 n명의 인원이 1차원 구간을 커버하는 데 이중에서 한 인원을 제외했을 때 커버가능한 최대 구간을 출력하는 문제이다. 전체 구간에서 하나를 제외 하였을 때 최대 구간을 구하면 되므로 하나의 구간에서 다른 구간에 영향을 받지 않고 유일하게 커버되는 구간 중 최솟값을 구하여 전체 구간에서 빼주면 답이 된다. 각각의 구간에서 독립적으로 커버하는 구간은 왼쪽에서 부터, 오른쪽에서 부터 , 두번 스위핑하여 구할 수 있다. 자세한 설명은 소스코드로 대신하겠다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include using namespace s.. 더보기 BOJ)14965 Lozinke 문제: icpc.me/14965 n개의 문자열이 주어질 때, 모든 문자열 s에 대해, s의 substring 중에 현재 보는 문자열을 제외한 나머지 문자열이 되는 개수를 전부합하여 출력하는 문제이다. 직접 비교하면 n^2으로 시간초과를 보게된다. 문자열의 길이가 10이하라는 사실을 이용하여 모든 문자열 s를 해싱해준 뒤 마찬가지로 모든 문자열의 substring을 전부 해싱하여 set과 map을 이용하여 개수를 계산해주면 n*10*10*logn의 시간에 문제를 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include #include #in.. 더보기 이전 1 다음