Approach 전체 수의 크기가 65536정도밖에 안되는 상황이므로, k개의 숫자들 중 해당 숫자보다 작은 수의 개수를 질의하는 쿼리를 빠르게 응답해주면 된다. 잘 생각해보면 세그먼트 트리로 쉽게 구할 수 있다는 것을 알 수 있다. 또한 슬라이딩 윈도우 느낌으로 빠지는 부분은 -1, 들어오는 부분은 +1하는 방식으로 update해주면 된다. 추가적으로 위 방식대로 진행하게 되면 0 ~ 특정한 수까지 고려했을 때의 개수가 중앙값 보다 작은 경우와 그렇지 않은 경우가 이분법적으로 갈리게 되므로 이분탐색으로 중앙값을 쉽게 도출할 수 있게 된다. Code #include #define fastio cin.tie(0)->sync_with_stdio(0) using namespace std; using ll = ..

Approach 일단 처음 접근한 방법은 세그먼트 트리 + 이분 탐색이다. 잘 생각해보면 bitwise or 계산 결과는 단조증가할 수 밖에 없다. 구간의 시작점을 1 ~ N까지 이동시키면서, lower_bound를 해서 k가 나오면 해당 구간을 출력해주면 된다. 구간 별 xor 결과는 세그먼트 트리를 통해서 관리를 하고, 이를 이분탐색으로 만족하는 구간이 있는지를 파악해주면 된다. 대회가 끝나고 공식 해설을 보고, 다음과 같은 방법으로 풀면 좀 더 쉽게 처리할 수 있음을 파악하였다. 잘 생각해보면, k와 xor한 결과가 k이면 구간 안에 들어갈 수 있는 수이고, 그렇지 않으면 무조건 들어갈 수 없는 수이다. 따라서, 들어갈 수 있는 숫자들을 전부 다 더했을 때 k가 나오면 문제조건을 만족할 수 있는 구..

Approach key와 value가 등장하는 상황이므로 Map을 활용하면 된다는 것은 쉽게 추측할 수 있다. 이 문제에서 가장 독특한 지점은 가장 가까운 key값에 매핑한다는 것인데, 이 부분은 Map 안에 존재하는 lower_bound나 upper_bound method를 활용해서 구해주면 된다. 다만, 해당 method를 통해 구해준 iterator가 begin()이나 end()와 같은 경우만 예외처리를 잘 해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int n, m, k; map s; int find_key(int t){ if(s.lower_b..

Approach 문제 상황을 재구성해보면 존재하는 맛 중에 경계값에 위치한 맛을 찾아주면 된다. 상황 자체는 https://viyoung.tistory.com/246 와 근본적으로 동일하다. [백준 19646번] [세그먼트 트리] Random Generator Approach "dp[i] : i번째 수까지 활용했을 때 존재하는 수"라고 잡아서 dp로 풀 수 있을 것처럼 보이지만 이 문제는 업데이트가 자주 나오고 있는 상황이므로, dp 값이 계속 바뀐다. 따라서 이 문제는 dp viyoung.tistory.com 위 문제의 경우는, 경계값을 찾가나가되 업데이트 과정에서 해당 숫자들을 모두 지워주는 형태이다. 반면 이 문제의 경우는 -1을 업데이트 처리해주면 된다. 근본적인 문제의 접근 방법 자체는 완전히 ..

Approach 이 문제의 예시로 제공된 수에서 위치를 가장 판단하기 쉬운 것은 8이다. 왜 8이 가장 마지막 자리에 있는지를 생각해보면 자기보다 작은 수가 한 개도 없고, 가장 큰 숫자이므로 가장 뒤에 오는 것이다. 마찬가지로 7의 경우를 판단해보면 뒤에서부터 남은 자리 중 2개를 건너뛰고 앉으면 된다. 즉, 이를 통해 구간합을 관리하고 있다는 느낌을 받으면 된다. 추가적으로 큰 수부터 작은 수로 자리를 채워나가면서 업데이트 해주면 된다. 다만, 해당 자리가 어딘지를 판단해주기 위해서는 이분탐색으로 파악해주면 된다. 느낌이 https://viyoung.tistory.com/246 와 정말로 비슷하다. 이분탐색을 통해 쿼리의 인덱스를 찾는 느낌이 매우 유사하다. [백준 19646번] [세그먼트 트리] R..

처음에는 MAX값을 변수로 두고, 최종 결과까지 가면서 남아있는 체력이 0 초과하기 위한 범위를 구하고 이 중 최솟값을 출력하는 방식으로 구현하려고 하였다. 사실 구현 양상을 보면 충분히 가능해보인다. 다만, 다른 방법으로는 가장 최악의 경우 몬스터가 엄청 쎄고 용사는 매우 약하다고 가정해보면 123456개의 방에서 몬스터의 공격력은 1000000이고, 체력도 1000000인데 용사의 공격력은 1이라고 하면 이 경우 최대 hp는 이 3개의 값을 곱한 값이다. 즉, HP는 1과 위의 최대 hp 사이에 존재할 수 밖에 없는 것을 활용해서 직접 다 계산해주면 된다. 최대 HP를 k라 하면 시간 복잡도는 O(nlgk)이므로 충분히 시간안에 돌아간다. #include #define fastio ios_base::..

사실상 백준 2792번 보석상자와 다른 부분이 하나도 없다. 물론 정렬하기는 해야한다는 점에서 차이가 아얘 없지는 않다. viyoung.tistory.com/186 [백준 2792번] [이분 탐색] 보석 상자 잘 생각해보면, 특정한 수를 나누고 몫과 나머지와 관련있다는 사실까지는 쉽게 파악할 수 있다. 다만, 해당하는 숫자를 판단하기 위해서 10e9 숫자를 판단해야하는데 이 부분은 이분탐색으로 해 viyoung.tistory.com 특정한 숫자 간격을 얼마만큼 형성할 수 있는지를 묻는 것이므로 근본적으로 나눗셈과 관련이 되어있다. 적당히 몫과 나머지를 보고 연산을 해주면 된다. 기존에 있는 주유소에는 다시 설치할 수 없으므로 나머지가 0인 경우에는 몫에서 - 1개만큼의 신규 주유소를 지을 수 있는 것이고..

잘 생각해보면, 특정한 수를 나누고 몫과 나머지와 관련있다는 사실까지는 쉽게 파악할 수 있다. 다만, 해당하는 숫자를 판단하기 위해서 10e9 숫자를 판단해야하는데 이 부분은 이분탐색으로 해결할 수 있음을 알 수 있다. 추가적으로 만족하는 상황 중에 가장 작은 숫자를 찾는 것이므로 lower_bound를 물어보는 것이다. 따라서 lower_bound binary search를 진행해주면 된다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef long long ll; int main(void){ fastio; ll n, m; cin >> n >> m; vector ..