Precomputation
-
BOJ 18622 DedenneProblem Solving/Solution Sketch 2020. 5. 8. 20:22
BOJ 18622 Dedenne (GP of Warsaw, Petrozavodsk Programming Camp Summer 2019 Day 5 #D) 3일 정도에 걸쳐 5시간정도 고민했고, 찾아낸 풀이가 매우 인상적인 문제였다. 우와 정말 데덴네~ 문제 설명 쿼리 $T$개가 주어진다. ($1 \leq T \leq 50000$) 각 쿼리마다 정수 $N$이 하나씩 주어지는데, 문제에서 주어진 Cost가 최소가 되도록 조건에 맞게 $N$개의 Binary String을 선택해야 한다. ($2 \leq N \leq {10}^{15}$) 조건은 1. 선택한 모든 Binary String에서 연속한 두 자리에 모두 0이 올 수 없다. 2. 선택한 한 Binary String이 다른 Binary String의 Pre..