[백준] UCPC 연습 - 1

2025.06.29 토요일에 ANA 동아리 주최 UCPC 연습 1회차를 진행했다.
뉴비분들도 있어서 문제셋은 골드로 선정했다.
3시간을 가졌고, 나는 뉴비분들 도와주면서 3문제를 해결했다.

17374번: 비트베리

boj.kr/17374

최종적으로, 비트코인을 얻기 위해 비트, 코인이 필요하다.
베리는 모두 코인으로 바꾼다 <- $Q/C*D$
교환 비율 비트 : 코인 = $A$ : $B$ 를 사용하여 비트코인을 최대한 만들기 위해,
교환 비율로 $x\ (x\in Z)$번 거래를 했다고 하자.
내가 갖는 비트와 코인은 각각 $P+Ax$, $Coin-Bx$ 이다.
처음에, 비트코인을 최대로 갖기 위해 비트, 코인의 개수가 동일하면 좋다고 생각 -> 이차식으로 $(P+Ax)(Coin-Bx)$의 값이 최대가 될 때라고 생각했지만 아니었다.
$P+Ax = Coin-Bx$ 인 경우를 조사하면 된다.
$x$가 정수임을 보장하기 위해 내림함수와 그 부근을 조사한다. $\lfloor x-1 \rfloor, \lfloor x \rfloor, \lfloor x+1 \rfloor$ 중 비트코인 개수의 최대값을 확인한다.

25393번: 교집합 만들기

boj.kr/25393

주어진 구간을 여러 개 사용하여 특정 구간을 만들기 위해서는 최대 2개의 구간만 필요하다.
교집합이기 때문에 $[l, r]$을 만들기 위해 2가지 경우만 존재한다.
1. $[l, r]$이 존재
2. $[x, r]$와 $[l, y]$이 존재

처음에는 주어진 구간을 정렬시키고 이분탐색으로 찾아내려고 했다.
근데 앞의 hhs라는 사람이 vector를 유지하면 편할 것 같다고 했다.
해시(딕셔너리) $upper$, $lower$를 사용하여, 구간 $[l, r]$ 이 주어질 때, $upper[l].add(r)$, $lower[r].add(l)$과 같이 저장한다.

Query로 $[a, b]$가 들어온다고 할 때, $upper[a][i] >= b$, $lower[b][[j] <= a$를 만족시키는 $(i, j)$가 존재한다면 $[a, b]$를 만들 수 있다.
$upper[a]$, $lower[b]$의 값이 오름차순으로 되어 있다면, $i=upper[a].length$, $j=0$으로 검사하면 된다.
그러나, $N$개의 구간 중 정확히 $[a, b]$가 존재하는지 확인하려면 $upper[a][x] = b$ 또는 $lower[b][y] = a$일 때의 $x$ 또는 $y$를 확인하면 된다. 이 문제는 마찬가지로 오름차순이면 이분탐색으로 구할 수 있다.

최종적인 시간복잡도는,
$upper$, $lower$ 구성에 $O(NlogN)$, 쿼리 하나에 O$(logN)$으로,
$O((N+Q)logN)$ 으로 해결할 수 있다.

17370번: 육각형 우리 속의 개미

boj.kr/17370

처음에는 DP인 것 같았다. $N$이 작은 것을 보면 완탐도 고려할만 해보인다.
쭉 읽어보니까, 한 번 이동에 경우의 수가 2가지 존재한다.
$N$의 값을 증가시키며 시뮬레이션을 하여 규칙을 찾으려 했으나, 수가 커질수록 상당히 복잡해진다.

페로몬을 고려하지 않고 이동하면 $2^{22}$가지의 경우의 수가 나온다.
이는 나이브로 해도 시간적으로 충분하다.
그냥 백트래킹으로 구현하면 쉽겠으나.. 그래프를 육각형 벌집모양으로 그래프를 잘 정의하고 dx, dy를 이용해주면 쉽게 해결된다.