11월의 문제 풀이 - (2)

11/11 ~ 11/20에 푼 문제들입니다.

문제의 풀이가 포함되어있으니 유의하세요.

 

---

11/11

BOJ 10216 - Count Circle Groups

Gold 4

 

#geometry   #disjoint_set

 

$O(N^2)$에 간선을 생성해주고, 컴포넌트 개수를 세주면 된다.

---

11/12

BOJ 30510 - 토마에 함수

Gold 1

 

#Euler's_totient_function

 

$1 + \sum \limits_{i=1}^{\lfloor \frac{Q}{P} \rfloor} \phi{(i)}$을 구해주면 된다.

---

11/13

BOJ 14451 - 안대 낀 스피드러너

Platinum 5

 

#bfs

 

위를 보는 상태와 오른쪽을 보는 상태를 시작으로, 두 점을 동시에 움직이며 bfs하면 된다.

상태 1의 $x, y$좌표 및 방향, 상태 2의 $x, y$좌표 및 방향으로 총 6개의 인자가 전체 상태에 영향을 준다.

따라서 이를 관리하는 6차원 배열로 해결할 수 있다.

---

BOJ 28688 - 로봇융합관 건설

Platinum 2

 

#game

 

$N \le 2$ 혹은 $M \le 2$이면 항상 선공이 이긴다. 후공이 선공의 가로줄을 막으면 반드시 세로줄이 완성되고, 세로줄을 막으면 반드시 가로줄이 완성되기 때문이다.

$N > 2, M > 2$인 경우만 고려해보자.

 

i) $N, M$이 모두 홀수인 경우

초기에, 후공이 1행에 놓는 경우는 선공도 똑같이 1행에 놓고, 후공이 2행에 놓는 경우엔 선공이 그 위로 놓으면 선공이 반드시 3행의 가로줄을 먹을 수 있다. 따라서 항상 선공이 이기게 된다.

 

 ii) $N, M$ 중 짝수가 있는 경우

선공의 i)에서의 전략이 통하는 이유는, 항상 최선의 수를 놓아도 2행을 처음 먹는 사람은 반드시 후공이기 때문에 선공이 3행을 먹을 수 있던 것이다.

$N$이 짝수이면, 같은 전략으로 2행을 처음 먹는 자가 선공이 되고, $M$이 짝수이면 같은 전략을 써도 선공의 위에 추가로 후공이 한 번 더 놓을 수 있기 때문에 어떤 수를 두더라도 선공이 이길 수 없다.

 

사실, $N$은 홀수이고 $M$은 짝수일 경우에는 엄밀히 해보지 않고 proof by AC를 받았다. 그래서 ii)에는 잘못된 아이디어가 포함되었을수도 있다.

---

BOJ 1732 - 레이저

Gold 2

 

#geometry   #map   #sorting

 

기울기가 같은 점들에 대해, 점들의 $x$좌표와 높이를 pair로 저장해놓자.

$x$좌표가 원점에 가까운 순서대로 정렬해서 높이를 비교하며 가려지는 애들을 구하면 된다.

---

11/14

BOJ 11867 - 박스 나누기 게임

Silver 2

 

#game

 

둘 중 하나라도 짝수면, 선공이 짝수를 살려 (1, 홀수)로 분해할 수 있고 이렇게 하면 선공이 무조건 이긴다.

모두 홀수면, 선공이 어떻게 나누어도 반드시 (짝, 홀)로 분해되고 위의 방법을 적용하면 후공이 무조건 이기게 된다.

---

BOJ 14445 - 케이크(?) 자르기

Silver 1

 

#ad_hoc

 

$N$이 $2^i$꼴이 아닐 때 어떻게 해야하지 고민했는데,

그냥 $2^i > N$인 가장 작은 $i$에 대해 $2^i$개로 나누고 남은 건 버리면 된다..

---

11/15

BOJ 24124 - 高速道路 (Highway)

Diamond 5

 

#segtree   #hld

 

1을 루트로 정했을 때를 기준으로 1과 가까워지는 방향은 $up$, 1에서 멀어지는 방향은 $down$의 가중치를 부여한다고 새로 정의하자.

상행선과 하행선으로 주어진 $s, t$에 대해, 부모 자식의 대소 관계를 이용해 $s, t$를 $up, down$에 알맞게 갱신해주면 된다

---

11/18

BOJ 15647 - 로스팅하는 엠마도 바리스타입니다

Platinum 5

 

#tree_dp   #dfs

 

다른 정점에서 어떤 한 정점에서 다른 모든 정점까지의 거리의 합을 구하는 문제가 이 구간에 많이 보이는 것 같다.

그 값을 dp[i]라고 하면, dfs 2번으로 dp 테이블을 완성할 수 있다.

---

11/19

BOJ 23257 - 비트코인은 신이고 나는 무적이다

Gold 3

 

#dp

 

$i$개를 골랐을 때 나올 수 있는 값들은 최대 1024개이다. 여기에 최대 100개의 수들을 xor해도, 나올 수 있는 값은 최대 1024개이다.

길이 1024의 배열을 만들어서 $1 \le i \le M$에 대해 각 단계에서 가능한 값을 체크해두면 된다.

---

BOJ 22345 - 누적 거리

Gold 2

 

#sorting   #prefix_sum   #binary_search

 

쿼리에서 주어진 $x$를 기준으로 $x_i < x$인 $i$들과, $x_j \ge x$인 $j$들에 대해, 각각의 누적 거리를 합한 것이 $f(x)$가 된다.

$j$만 구하면 영역은 자연스레 두 구간으로 나뉘므로 $j$만 이분 탐색으로 구해주고, $f(x)$를 구성하는 식은 $a_i$의 누적 합, $a_ix_i$의 누적 합을 이용해 나타낼 수 있다.

$f(x) = x\sum \limits_{i=1}^{j} {a_i} - x\sum \limits_{i=j+1}^{N} {a_i} - \sum \limits_{i=1}^{j} {a_ix_i} + \sum \limits_{i=j+1}^{N} {a_ix_i}$

---

11/20

BOJ 6523 - 요세푸스 한 번 더!

Gold 2

 

#map

 

한 사람이 두 번 걸리게 되는 경우까지의 스텝 수가 $1,000,000$ 이하라고 명시되어 있기 때문에 여기까지만 세주면 된다.

한 사람이 두 번 걸린 이후부터는 쭉 걸렸던 사람만 걸리니까, 전체 사람 수에서 두 번 이상 걸리는 사람 수만 빼주자.

---

BOJ 19577 - 수학은 재밌어

Platinum 5

 

#Euler's_totient_function

 

$x\phi(x) = N$이려면, $x$는 $N$의 약수이어야 한다.

$N$이 $10^9$에 가까워지더라도, $x\phi(x) = N$이 되려면 둘의 차이가 극도로 심하지 않을 거란 추측을 했다.

실제로 $1,000,000$ 이하의 모든 수에 대해, $\sqrt{x} > \phi(x)$인 경우는 없었다. 따라서 답이 존재한다면, 대략 $100,000$ 이하에 모두 존재하겠다라는 가정을 하고 풀었다.

---

BOJ 13124 - 순열 그래프의 전갈성 판별

Platinum 4

 

#case_work

 

순열이 전갈성을 가질 때 어떤 형태를 갖추고 있는지 잘 보자. 관찰만 잘 하면 쿼리 하나 당 $O(1)$에 처리할 수 있다.

해답을 적기엔 문제가 너무 쉬워져서 적지는 않겠다.