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

Approach 이 문제를 물론 네트워크 플로우를 활용해서 풀 수는 있는데, 그리디를 활용한 방법으로 접근해보자. 문제를 정확히 이해해보면, reordering 성질을 만족하는 것을 쉽게 파악할 수 있다. 예를 들어 다음과 같은 행렬이 있다고 하자. $$\begin{pmatrix} 1 &1 & 0 & 1 \\ 1 &0 &1 &1 \\ 1 &1 &1 &1 \\ 1&1 &1 &1 \end{pmatrix}$$ 행과 열의 합을 유지한 상태로 1로 표시된 2개의 element의 위치를 변경할 수 있다. 예를 들어, 첫번째 row vector의 2번째 element대신 3번째 element를 1로 만든 뒤 두번째 row vector의 2번째 element를 1로 만들고 3번째 element를 0으로 만든다. 즉, ..

접근 방법 일단, 어차피 카드 묶음이 1개씩 지워지는 상황이므로 무조건 큰 숫자가 나중에 묶이는 것이 유리하다. 그렇지 않으면 반복해서 묶이게 되어 숫자가 더 커지기 때문이다. 따라서, 숫자가 작은 것을 먼저 선택하기 위한 자료 구조가 필요하므로 우선순위 큐 자료구조를 활용해주면 된다. 코드 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; int n; cin >> n; priority_queue pq; for(int i = 0; i > temp; pq.push(temp); } int res..

사실 이 문제는 백준 19580번 "마스크가 필요해"와 완전히 접근방법이 동일하다. viyoung.tistory.com/171 [백준 19580번] [그리디/ 우선순위 큐] 마스크가 필요해 문제를 보고 생각보다는 쉽게 그리디 문제임을 파악할 수 있다. 문제 조건을 잘 보면, 최대한 많은 시민이 마스크를 구매할 수 있도록 유도해야한다. 즉 상식적으로 이 워딩을 보면 모든 시민들 viyoung.tistory.com 왜냐하면, 9676번과 19580문제에서 가장 Tight하게 해당 value를 만족하는 것을 선택한다는 핵샘이 동일하기 때문이다. 이전 19580문제 해설에서 언급한 것처럼 책을 가질 수 있는 scope를 increasing order로 정렬하고, 책 또한 번호를 증가시켜가면서 책을 가질 수 있는..

잘 생각해보면, 주유할 수 있는 양이 무한대이므로 최소 가격으로 넣을 수 있을 때 최대한 많이 주유하는 것이 유리하다. 다만, 문제가 되는 지점이 현재까지의 최소 가격을 어느 상황까지 커버할 수 있는지가 미지수이다. 예를 들어 지역 1, 2, 3, 4를 방문하는 상황이라고 하자 지역 1에서 현재 기름을 3의 가격을 판매하고 있다고 하자. 일단 적어도 지역 2까지는 가야하므로 최소한 지역2까지 가는데 필요한 거리에 필요한 주유량은 구입해야 한다. 하지만, 그 이상의 거리까지 구매를 해야하는지 여부는 지역2의 기름 가격을 알아야 한다. 지역 2의 기름 가격보다 싸면, 지역 1에서 지역2에서 지역3까지 가는데 필요한 기름을 미리 구매하는 것이 더 유리하다. 즉, 지역 2에서 3으로 갈 때 사용되는 기름의 가격..

사실 잘 생각해보면, 작은 숫자들을 순차적으로 뽑아주면 된다. 우선순위 큐를 활용해주어도 괜찮고, 전체 쿼리의 업데이트가 없으므로 배열을 정렬해줘서 하나씩 탐색하는 방식으로 처리해주어도 무방하다. 다만 0이 여러개 등장할 수 있는 지점만 조심해주면 된다. (맨 앞자리가 0이 될 수 없으므로 2번째 자리 이후부터 0을 배치하면 된다. 즉 첫 자리는 0이 아닌 숫자를 무조건 배치하고 0을 고려해주면 된다.) #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; while(true){ int n; cin >> n; vector data; if(n..

일단 이 문제를 보고 DP의 대표적인 유형인 Napsack문제를 떠올릴 수 있으나 가방 1개 당 보석 1개만 챙길 수 있다는 점에서 해당 문제와 차이점을 보이고 있다. 처음 접근한 방법은 다음과 같다. 만약 무게를 감당할 수 있다면 무조건 무게를 큰 것을 우선적으로 고르는 것이 유리하므로, 무게를 큰 순서대로 배치하고 감당가능한 무게이면 챙기는 방식으로 진행하였다. 다만, 이런식으로 진행하게 되면 최악의 경우 각 가방에서 N개를 전체탐색해야하므로 O(NM)이 나와 시간초과가 나오게 된다. 근본적으로 시간 초과가 나는 이유가 각 가방에 대해서 보석을 전체 탐색을 하기 때문이다. 발상을 바꿔서 무게를 우선적으로 고려하면, 가방의 한계 무게를 넘지 않는 것 중 가격이 최대인 것을 골라주는 것으로 문제를 바꿔 ..

여러가지 샘플을 만들어가면서 최적해를 구해보면 1. 남는 플러그 자리가 있으면 들어간다. 2. 없는 경우 다시 등장하는 것이 이후인 것부터 뽑는다. 만약 다시 등장하지 않는 경우는 해당 값을 INF로 처리해서 최우선적으로 뽑으면 된다. 적당히 현재 어느 숫자가 플러그에 꽂혀있는지를 저장해두는 배열을 만들고 관리해주면 된다. 추가적으로 순차적으로 데이터가 들어오고, 앞에서부터 다음 자리의 크기 비교를 해야하는 상황이므로 큐 자료구조를 활용하면 쉽게 풀 수 있다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; #define INF 987654321 int main(void){ ..