풍선 맞추기 문제 N개의 풍선이 일렬로 놓여있고 화살을 쏴서 풍선을 맞추는 데 모든 풍선을 터트릴 수 있는 최소 화살의 개수를 구하는 문제이다. 화살은 처음 h 높이로 쐈다면 풍선 하나를 터트리면 h-1 높이로 바뀌어서 계속 날아간다. 화살은 왼쪽에서 오른쪽으로 쏜다. 문제 풀이 i번째 풍선을 직접 맞출지 다른 풍선을 거쳐서 맞추는지는 이 i번째 풍선 왼쪽으로 a[i]+1의 값을 가진 풍선을 맞췄는지 안 맞췄는지를 체크해주면 된다. 안 맞췄다면 i번째 풍선은 직접 화살을 쏴서 맞춰야 하는 풍선이므로 화살 개수를 ++해주면 된다. 아닌 경우는 a[i]+1의 값을 가진 풍선을 없는 것으로 바꾸고 a[i] 값의 풍선이 맞췄음을 갱신해주면 된다. 1차원 배열로 구현할 수 있다. 소스 코드 #include usi..
조세퍼스 문제 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..