문제 : https://www.acmicpc.net/problem/15460 s[0...n-1]에 주어진 score를 저장합시다. 이 문제는 k를 1부터 n-2까지 증가시키며, s[k]...s[n-1] 중 최솟값을 제외한 것의 평균을 최대로 하는 k들을 구하는 문제입니다. 최대 n이 100,000이므로 O(n^2)이 되면 안되는데, 다음과 같이 O(n)에 score의 부분합과 부분최솟값을 미리 구해놓으면 나중에 s[k]...s[n-1] 중 최솟값을 제외한 것의 평균을 O(1)에 구할 수 있습니다. a[i] : s[n-1]부터 s[i]까지 합. m[i] : s[n-1]부터 s[i]까지 최솟값. 그 다음부터는 k를 1부터 n-2까지 증가시키며, a[k] - m[k] / (n - k - 1)이 최대가 되는 k..
문제 : https://www.acmicpc.net/problem/16771 barn 1에 있는 10개의 bucket 중 하나를 사용해 우유를 옮기고, barn 2에 있는 11개의 bucket(방금 barn 1에서 2로 옮기는 데 사용한 bucket 포함) 중 하나를 다시 barn 1으로 옮기는 작업을 한 세트로 생각합니다. 이 세트를 2번 실행하면 모든 경우의 수를 탐색할 수 있습니다. 시간복잡도: O(N^4) (N: bucket의 개수) #include #include using namespace std; int bucket1[10], bucket2[10]; bool check[1199]; // 802~1198 void back_and_forth(int barn1, int depth) { if(dep..
문제 : https://www.acmicpc.net/problem/17200 input으로는 각 sub-population에 있는 소가 가진 특성들이 들어옵니다. 예제 데이터를 봅시다. 4 2 spots firebreathing 0 1 flying 2 telepathic flying sub-population #1은 spots, firebreathing 특성을 가지며, #2는 아무 특성도 가지지 않고, #3은 flying, #4는 telepathing flying 특성을 가집니다. sub-population #1에 해당하는 노드는 루트로부터 spots, firebreathing 간선을 거쳐서 도착해야 합니다. 다른 sub-population이 spots이나 firebreathing을 포함하고 있지 않으므..