오프라인 다이나믹 커넥티비티 알고리즘을 알아보자. Offline Dynamic Connectivity 는 간선 추가, 삭제를 오프라인으로 처리하는 문제에 쓰인다. 대표적으로 BOJ의 16911 = 16912 = 15316 < 12876 < 15946 순으로 문제가 어렵다. (16911,16912,15316 이 3개중 하나만 풀어도 나머지 2개는 꽁짜..) 여러가지 방법이 있겠지만 저는 분할 정복을 사용했습니다. (사실 1가지임 ㅋ) 일단 간선의 라이프 타임을 저장해 둡니다. (나타난 시간 ~ 사라진 시간) 생기고 지워진 적이 없다면 맨 마지막 시간으로 해둡니다. (나타난 시간 ~ 마지막 시간) 이제 분할정복을 해줄텐데 solve(l,r,Edge set) l~r : 간선 라이프 타임이 l~r 이고 m = ..
아무거나 제출해도 다맞진 않는다. 인생...참 빠르네
알고리즘은 그리디 입니다. 일단 제일 가격이 낮은 숫자들로 최대한 채웁니다. 이때, 0 이 제일 싼 가격이면 그 다음으로 싼 가격의 숫자를 맨 앞에 놓고 그 뒤에 0을 쭉 붙입니다. 그러면 쓰고 남는 돈이 있는데 이 돈으로 최대한 큰 수로 바꿉니다. 각 숫자에 대해 몇개씩 살 수 있는지 나오는데 이 숫자들을 내림차순으로 나열하면 제일 큰 숫자를 만들 수 있습니다. 제가 쫌 코드를 드럽게 짜기 때문에 풀이 이해용으로만 보시기 바랍니다. (못 볼듯...) #include using namespace std; typedef long long ll; int n,pl,End; ll k,x,co[15],ch[15],tmp[15]; struct Money { ll cost; int num; }a[15]; bool c..