조세퍼스 문제 2 문제 조세퍼스 순열을 구하시오! (1 ≤ M ≤ N ≤ 100,000) 문제 풀이 naive 하게 \(O(NM)\)에 풀 수 있다. \(sum[i]=\sum_1^i{alive[x]},\:(alive[i]=i번째 \:사람이 \:살아있으면 \:1 \:아니면 \:0)\) 라고 정의 하자. 현재 i번째 사람부터 시작한다면 제거된 사람을 제외하고 \(sum[j]-sum[i]=m\)을 만족하는 j값을 찾으면 된다. m값이 현재 남아있는 사람보다 큰 경우와 j인덱스가 한 바퀴를 돌아 i보다 작은 경우 두 경우만 처리를 해주고 찾게 되면 여전히 \(O(NM)\)이다. 하지만 \(sum[i]\)는 순 증가함수고 근이 한 개만 존재하기 때문에 parametric search를 사용할 수 있고 j값을 \(..
A. Anton and Polyhedrons 문제 다면체의 이름이 n개가 들어온다. 면들의 총합을 출력하면 되는 문제이다. 문제 풀이 각 다면체의 이름들의 첫 글자가 다르므로, 첫 글자만 비교하여 계산할 수 있다. 소스 코드 #include using namespace std; int n; char input[100]; int main(){ scanf("%d", &n); int ans=0; for(int i=0;ipriority priority) { NodePair splitted = split(root, node->key); node->setLeft(splitted.first); node->setRight(splitted.second); return node; } else if (root..