0과 1의 쉼터

문제https://www.acmicpc.net/problem/3653풀이위에서부터 아래 방향으로 영화 1 ~ N이 쌓여있을 때, M번의 쿼리에 대해 영화를 뺀다.이 때, 제거한 영화 위로 쌓여있는 영화의 수를 출력해야 한다.제거한 영화는 다시 맨 위에 쌓는다.만약 제거한 영화가 맨 위에 놓인 영화라면 당연히 쌓여있는 영화의 수는 0이다.영화의 위치가 매번 달라지므로 영화의 수, 즉 부분합을 계속 세어야 한다. M은 최대 100,000이므로 세그먼트 트리를 사용했다.리프 노드가 N개인 세그먼트 트리에 대해 i번 영화를 제거했다면, 1 ~ i - 1번 영화에 대한 누적합을 전부 갱신해야 한다.세그먼트 트리를 사용하는 의미가 없다.따라서, 리프 노드가 M + N개인 세그먼트 트리로 확장해 해결했다. i번 영화..

문제https://www.acmicpc.net/problem/2533풀이우선, 주어지는 루트가 없으며, 어디서 탐색해도 상관없다.그래프를 구성 후 dfs를 진행하자. 얼리 어답터의 수가 최소가 되도록 만드는 방법에 대해 알아보자.맨 처음 리프노드는 자기 자신이 얼리 어답터라고 가정해야 한다.하지만, 부모 노드가 존재한다면 리프 노드는 얼리 어답터가 아닌 상태가 정답이다.여기서 dp는 두 상태(EARAY, GENERAL)에 대해 고려해야 한다.dp[i][j] : 상태가 i일때 j ~ N에 필요한 최소 얼리 어답터의 수dfs를 통해 방문을 진행하면 방문 표시와 함께 현재 정점이 얼리 어답터인 경우를 세주자.리프 노드까지 도달 후 리프 노드들이 얼리 어답터라고 표시된 후 부모 노드로 돌아와서 부모 노드의 두 ..

문제https://www.acmicpc.net/problem/11966 풀이입력받은 N이 2의 제곱수인지 확인하는 문제다.N을 2로 나누었을때의 나머지가 1이면 2의 제곱수가 될 수 없다. 이 과정을 반복해주자만약 N이 2의 제곱수가 아니라면 N은 1이 될 수 없다. 이 점을 이용해 결과를 출력하면 된다.소스코드보기