옛날에 푼 문제들이지만 풀이를 해야 할 일이 최근에 생겼다.
해당 프로젝트에서 문제 풀이를 올리는 겸 블로그에 짧게 작성을 해보려고 한다.
이렇게라도 블로그에 포스팅 하는 버릇을 들이면 좋을 것 같다.
GPA (BOJ 21101)
생각할 수 있는 가장 심플한 DP를 생각해보자.
$D_{i,x}$ := $i$일까지 $A$ or $B$를 적당히 골라 sum이 $x$인 최대 행복한 날의 수
이때 복잡도는 $x$의 범위가 $nA_i$ 니 $4000 \times 400$으로 $O(n^2A_i)$로는 어림도 없다.
DP 테이블에 들어가는 값은 $n$이하이니 값과 인자를 뒤집는 테크닉을 사용해보자.
당연하지만 행복한 날이 같으면 합은 작을 수록 좋다.
$D_{i,j}$ := $i$일까지 $A$ or $B$를 적당히 골라 행복한 날이 $j$개인 최소 합
이제 테이블은 $O(n^2)$이고 전이는 $A$ or $B$ 상수 개니까 DP를 돌려주면 된다.
Clique Partition (BOJ 28054)
여담 : KAIST 봄 대회에 내가 직접 출제한 문제다.
$K_n$의 간선 수는 $\binom{n}{2} = (n-1)\frac{n}{2}$이다.
$n$짜리 트리는 간선이 $n-1$개니까 $\lceil \frac{n}{2} \rceil$ 개가 하한이고 그게 최소라고 추론할 수 있다.
$n$이 짝수라고 생각하고 풀자. 홀수는 그냥 ceiling이니까 $n-1$로 풀고 성게를 붙이면 ok.
이제 컨스트럭션을 생각하면 되는데 답은 체인을 생각하면 접근하기 쉽다.
$1$번 점에서 정점 번호를 $2, n, 3, n-1, 4, \cdots$ 과 같은 순서로 이어주자.
번개 모양이 그려지는데 이걸 $\frac{n}{2}$개 시작점을 돌려가면서 겹치면 전체가 된다.
맥스웰의 악마 (BOJ 24033)
여담 : 경곽 송년 대회에 내가 직접 출제한 문제다.
일단 문제가 무슨 소리를 하는건지 이해를 해야 한다.
칸막이를 닫아둔 채로 오른쪽 관에만 집중해서 보면 관에는 (위치, 방향)이 총 $2R$개 있다.
그리고 초기 상태를 기준으로 저 상태들이 하나씩 차례대로 칸막이에 갖다 박는다.
갖다 박는 순서를 기준으로 $1$부터 $2R$까지 넘버링을 하고, 왼쪽도 똑같이 해주자.
이제 칸막이를 어떤 시점에 열면 그때 왼쪽에서 박는 상태와 오른쪽에서 박는 상태의 입자 무게 합이 뒤바뀌게 된다.
따라서 우리의 문제는 적절히 바꾸기를 수행해서 오른쪽 상태들에 큰 값을 주는 것이다.
어떤 칸들이 서로 부딪히는 지를 생각해보자.
방법 1. 관찰하기
$L=4, R=2$라고 하고 한 번 부딪히는 상태들을 지켜보자.
(1, 1) (2, 2) (3, 3) (4, 4) (5, 1) (6, 2) (7, 3) (8, 4)
그리고 이걸 다른 $L, R$에 대해서도 같은 식으로 까보면 자연히 규칙을 알 수 있다.
그 규칙이 뭔지는 방법 2에서..
방법 2. 수식
시점 $t$에 부딪히게 되는 쌍은 $(t \; mod \; 2L, t \; mod \; 2R)$이다.
$a$와 $b$가 부딪히는 시점이 존재하려면 $a + 2Ls = b + 2Rt$의 자연수 해 $(s, t)$가 있으면 된다.
$2Ls - 2Rt = b-a$으로 정리할 수 있고 이거 베주 항등식이다.
$s, t$의 해가 존재할 조건은 $b-a$가 $2L$과 $2R$의 gcd의 배수임과 동치이다.
즉, $g = gcd(2L, 2R)$ 일때 $a \; mod \; g = b \; mod \; g$면 두 상태의 값을 바꿀 수 있다.
결론이 약간 그럴싸 해서 방법 1처럼 관찰해도 풀 수 있다.
이제 $a \; mod \; g = b \; mod \; g$를 만족하는 모든 칸을 자유롭게 바꿀 수 있다는 사실을 안다.
mod 값을 기준으로 $0, \cdots , g-1$ 각각에 대해 따로 풀자.
별건 없고 오른쪽에는 그런 칸의 개수가 $\frac{2R}{g}$개니까 왼쪽과 오른쪽을 합쳐 mod별로 가장 큰 $\frac{2R}{g}$개의 합을 구하면 끝이다.
완전히 같은 상태를 갖는 여러 점이 있을 수 있다는 함정이 있으니 잘 짜보자.
LRH 식물 (BOJ 2943)
잘 변형해보면 문제가 이렇게 바뀐다.
- 처음에 0으로 꽉 찬 길이 10만짜리 배열 $A$가 있다.
- $l, r$이 주어지면 $A_l + A_r$개의 꽃이 피고 $A_l$과 $A_r$은 0이 된다.
- $(l, r)$에 1씩 더한다.
구간 덧셈과 점 쿼리니까 이를 그냥 레이지 세그 같은 자료구조로 잘 구현하면 된다.
개인적인 선호는 펜윅으로 관리하는 것이다.
구간에 값을 더하는 대신 시작점에 1 더하고 끝점에 1 뺀 다음 점의 값 구하기는 1번부터 합을 구해버리자.
구간 합 쿼리가 아니라 점의 값만 물어보니까 이것만으로 충분하다.
이렇게 짜면 400바이트 안으로 들어오니 숏코딩이 좋다면 참고…
지진 (BOJ 2126)
최적화 할 함수가 분수 꼴이라서 단순하게 MST를 돌리는 걸로는 안 풀린다.
분수 꼴 함수를 최적화할 때는 파라메트릭 서치를 한 번쯤 생각해보자.
시간 당 이득이 $k$를 넘는 해가 존재할까? 라는 결정 문제를 생각하고 식을 풀어보자.
$\frac{F - \sum c_i}{\sum t_i} \ge k$
이 식에서 분수가 보기 싫다면 그냥 정리해버린다는 해법이 있다.
$F - \sum c_i \ge \sum kt_i, F \ge \sum (c_i +kt_i)$
정리가 됐으니 그냥 $k$를 정했을 때 $c_i +kt_i$를 간선의 가중치로 하고 MST를 돌려서 합이 $F$를 넘는지 보면 결정 문제가 풀린다.
답이 실수 출력이니까 그냥 실수로 파라를 한 200바퀴 돌리면 된다.
Paths (BOJ 15866)
주목할 사실은 $K$가 5 정도로 매우 작다는 점이고 따라서 경로의 길이도 5를 넘을 수가 없다.
아무 점에서 시작해서 인접해 있고, 아직 방문하지 않은 색깔로 이동을 반복하면 당연히 심플 패스가된다.
이를 이용해서 각 색의 방문 여부를 상태로 DP를 수행하자.
$D_{u,s}$ := 현재 $u$번 정점에 끝 점이 있고 bitmask로 표현한 색깔 방문 여부가 $s$인 경우의 수
bitmask는 그냥 5bit로 32개 상태 표현을 해주면 $32 \times 300000$ 정도는 문제가 없다.
전이는 $s$가 작은 것부터 무식하게 돌면서 인접한 점 $v$가 $s$에 없는 색깔 $j$이면 $D_{v,s|(1<<j)} += D_{u,s}$를 수행해주면 된다.