공부가 필요해

BOJ 16076 휴식이 필요해 문제를 아는가? 이 문제에 제출하기만 하면 24시간 동안 백준의 모든 문제에 제출이 불가능하다.

요즘 백준을 너무 많이 하는 것 같아 이 문제를 이용해 스스로 제약을 걸어보려고 한다. 일단 목표는 하루에 한 번씩 꾸준히 제출을 해 시험 전까지 더 이상 백준을 하지 않는 것이다.

 

으윽

 

 이런다고 해서 내가 공부를 열심히 할지 아니면 부계정을 만들어서 다이아 파밍을 하고 있을지는 장담할 수 없지만, 적어도 백준에 들어올 때마다 뭔가 느끼는 게 있길 바란다.

 

 

바로 오늘, 루비 두 문제를 풀어내면서 약 두 달 간의 루없찐 생활을 청산했다. 내가 해결한 것은 수열과 쿼리 25와 Bitwise Queries로 세그트리 비츠를 이용하는 문제이다. 각 노드가 가져야 하는 값은 mx, andv, orv로 쉽게 예상할 수 있지만, 쿼리의 성질을 관찰하여 중단 조건과 태그 조건을 정해주는 것이 쉽지 않았다. 이 조건을 찾았더라도 비트별로 나누어서 생각한다면 쿼리 당 log^2N이 걸릴 것 같아서 조금 부담스러웠다. (난이도가 루비인 만큼 log^2N으로는 안될거라 생각했다) 이를 logN으로 줄일 방법을 어제 자습 시간 내내 고민했지만 bitwise and 쿼리를 처리하지 못했다. 그러다 오늘 아침에 씻으면서 괜찮은 방법이 떠올랐고, 아침을 먹고 나서 이를 구현하니 다행히 1트에 AC를 받을 수 있었다. (사실 자체 제작 데이터로 수많은 디버깅을 거쳤다.) Bitwise Queries는 max를 min으로 바꿔주면 맞을 수 있다.

다른 분들의 코드를 보니 lazy를 전파하는 방법이 가지각색이었고, 나와 비슷한 방식은 거의 찾을 수 없었다. 그래도 fastio 없이 실행시간 각각 3등 / 2등 을 먹은 걸 보면 나름 효율적인 코드를 짠 것 같아 뿌듯하다 ㅎ

 

시험이 3주 남았다. 공부하자!