www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 유니온 파인드를 이용하여 처음으로 사이클이 만들어졌을 때를 찾았다. ranks를 이용해 트리의 깊이를 작게 만들어서 유니온 파인드 시간을 줄였다. 코드 #include #include #include using namespace std; int n, m; vector parent(500000); vector ranks(500000); void Pre() { for (int i = 0; i < n; i++)..

www.acmicpc.net/problem/7287 7287번: 등록 첫 줄에 자신이 맞은 문제의 수, 둘째 줄에 아이디를 출력한다. www.acmicpc.net 자신이 맞은 문제의 수와, 자신의 아이디를 출력 코드 #include #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); cout

www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net n이하의 수들을 제곱한 값을 미리 저장해 놓은 뒤, 각각의 수가 n을 제곱수의 합으로 표현될 때 제곱수로 사용하는지 확인하여, n을 제곱수의 합으로 표현할 때 제곱수의 개수가 최소가 되는 개수를 구한다. 코드 #include #include #include using namespace std; vector number2(50001, 0); vector cache(50001, ..

www.acmicpc.net/problem/17521 17521번: Byte Coin 입력은 표준입력을 사용한다. 첫 번째 줄에 요일 수를 나타내는 양의 정수 n과 초기 현금 W(1 ≤ n ≤ 15, 1 ≤ W ≤ 100,000)가 주어진다. 다음 n 개의 줄에서, i번째 줄은 i일의 바이트 코인 가격을 나 www.acmicpc.net 처음일 때, 마지막일 때, 중간지점일 때의 상황을 고려하여 코인을 사고파는 선택을 한다. 코드 #include #include #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); int n; long long w; long long b_coin = 0; vect..

www.acmicpc.net/problem/17520 17520번: Balanced String 0과 1로 이루어진 이진 문자열 0101101은 0과 1의 개수의 차이가 1 이하이다. 뿐만 아니라, 첫 번째 문자를 포함하는 모든 부분 문자열 0, 01, 010, 0101, 01011, 010110, 0101101 모두 0과 1의 개수의 차이가 1 이 www.acmicpc.net 이진 문자열이 아무것도 없는 상태부터 시작하여 0의 개수와 1의 개수가 같을 때, 0의 개수가 더 많을때, 1의 개수가 더 많을때를 고려하여 상황에 맞게 균형 잡힌 문자열을 만드는 숫자를 넣어가며 총개수를 센다, 0의 개수와 1의 개수가 같을때는 0과 1 모두 추가할 수 있는데, 이때 0을 추가했을 때와, 1을 추가했을 때 각각 ..

www.acmicpc.net/problem/17976 17976번: Thread Knots Your program is to read from standard input. The input starts with a line containing one integer, n (2 ≤ n ≤ 100,000), where n is the number of threads. In the following n lines, the i-th line contains two integers xi (0 ≤ xi ≤ 109) and li (1 ≤ www.acmicpc.net 이분 탐색, 파라메트릭 서치, 결정 문제로 mid가 가장 가까운 두 매듭 사이의 거리가 될 수 있는지 확인하여 가장 가까운 두 매듭 사이의 거리가 최대인 ..