본문 바로가기

백준

 (223)
백준 1280 - 나무 심기 https://www.acmicpc.net/problem/1280 힌트 1 더보기 특정 구간에 존재하는 나무의 개수와 위치의 합을 보존한다. 특정 구간에 존재하는 나무의 개수를 활용해서 이전에 심어진 나무와의 거리 합을 빠르게 구하는 방법을 생각해본다. 힌트 2 더보기 i를 이전에 심은 나무의 index, X는 현재 나무를 심을 index라고 하자. 심을 나무와 심어진 나무들의 거리 합은 다음 식으로 표현할 수 있다. $sum = \sum_{i = 1}^{X - 1}|tree_i - tree_X|$ 해당 식은 다음과 같이 바꿀 수 있다. $sum = |\sum_{i = 1}^{X - 1}tree_i - \sum_{i = 1}^{X - 1}tree_X|$ 이 식을 구현할 방법을 생각해본다. 풀이 더보기 i..
백준 13537 - 수열과 쿼리 1 https://www.acmicpc.net/problem/13537 힌트 1 더보기 수열의 원소를 바꾸는 연산은 없다. 힌트 2 더보기 수열의 갱신이 없는 상태에서 특정 구간의 원소 index를 빠르게 찾기 위해 Merge Sort Tree를 이용할 수 있다. 풀이 수열이 주어지고 특정 구간에서 k보다 큰 원소를 찾는 연산을 최대 10만 번 수행한다. 따라서 해당 연산을 빠르게 수행할 필요가 있고, Merge Sort Tree가 이를 가능케 한다. 머지 소트 트리를 구현해서 k보다 큰 원소가 나타나는 index를 upper bound로 찾으면 특정 구간에서 k 이하 원소의 개수를 확보할 수 있다. 우리는 k보다 큰 원소의 갯수를 알고 싶으므로 (구간의 길이 - 머지 소트 트리의 질의로 찾은 k 이하 원소..
백준 10728 - XOR삼형제 1 https://www.acmicpc.net/problem/10728 대회 에디토리얼에 의하면 이 문제는 백트래킹 사용을 염두에 두고 나온 것으로 보인다. 다만 백트래킹으로 문제를 푸는 것은 그다지 의미가 없다고 판단되어 제한이 더 큰 XOR삼형제 2에도 쓸 수 있는 솔루션을 동일하게 적용했다. 여기에서 확인할 수 있다.
백준 10736 - XOR삼형제 2 https://www.acmicpc.net/problem/10736 수열의 최대 길이 찾기 XOR의 성질에 따라 $V \oplus V = 0$ 이므로 XOR 과정 중 중복되는 수를 만나서는 안된다. 다시 말해 어떤 세 원소를 선택하든 최소 한 개의 비트를 살릴 수만 있으면 된다는 것이다. 그렇다면 100 이하의 수로 구성할 수 있는 수열의 최대 길이는 어떻게 찾을 수 있을까? 32와 64를 이진수로 나타낸 표를 보면서 생각해보자. X 1 0 0 0 0 0 1 0 0 0 0 0 0 이 표에 존재하는 0을 0 혹은 1로 채우는 경우의 수를 만든다고 했을 때 1이 절대로 들어가서는 안 되는 경우가 무엇일까? X 1 0 0 0 0 0 1 NO 0 0 0 0 0 바로 64에서 $2^{5}$에 해당하는 비트이다. ..
백준 13555 - 증가하는 부분 수열 https://www.acmicpc.net/problem/13555 17409 - 증가 수열의 개수와 풀이가 같다. 다만 17409와 달리 원소의 상한과 수열의 길이가 불일치라는 것과 세그먼트 트리가 아닌 펜윅 트리로만 풀린다는 점을 유의하여 구현하도록 한다. 전체 코드 더보기 #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include using namespace std; #define mod 5000000 int n, k; int dp[51][100001]; int sum(int pos, int seq) { if (!seq) return 1; int ret = 0;..

티스토리툴바