BOJ 문제풀이 (W29~30)

요즘 ps에 할애하는 시간이 눈에 띄게 적습니다.

핑계아닌 핑계를 대보자면 인턴 시험, 면접이 어마어마하게 많고(공채보다 더 많습니다) 프로젝트도 마무리 지었어야 해서 바쁘게 지나갔네요(덤으로 발바닥에 구멍이나서 병원을...)

 

아무튼 시작하겠습니다(27주차도 안까먹고 올리겠습니다 문제는 하나빼고 다 풀었습니다)

 

14739 faster sorting

//minrun이 주어졌을때 정렬은 $Nlog(N)$안에 가능합니다.

이를 증명하는 일이 문제풀이의 핵심인데 다음에 추가하겠습니다.

 

19587 객실배치

D[n, i] : N층의 i에 배칠 할 수 있는 경우의 수

위와 같이 배열을 정의 해주면 아래와 같은 점화식을 만들 수 있습니다.

$$\begin{pmatrix}
D_{N+1, 0}\\ 
D_{N+1, 1}\\ 
D_{N+1, 2}
\end{pmatrix} = \begin{pmatrix}
1 & 1 & 1 \\ 
1 & 0 & 1 \\ 
1 & 1 & 0
\end{pmatrix}\begin{pmatrix}
D_{N, 0}\\ 
D_{N, 1}\\ 
D_{N, 2}
\end{pmatrix}$$

 

 

 

또 식을 정리를 해보면 아래와 같아집니다.

 

$$\begin{pmatrix}
D_{N+1, 0}\\ 
D_{N+1, 1}\\ 
D_{N+1, 2}
\end{pmatrix} = \begin{pmatrix}
1 & 1 & 1 \\ 
1 & 0 & 1 \\ 
1 & 1 & 0
\end{pmatrix}^{N-1}\begin{pmatrix}
D_{1, 0}\\ 
D_{1, 1}\\ 
D_{1, 2}
\end{pmatrix}$$

 

하지만 N이 1e18이라 그냥 계산을 해주면 안됩니다.

저는 분할정복을 통해 이를 계산하였습니다.

log2(1e18) < 100임으로 시간안에 계산 할 수 있습니다.

 

2602 돌다리 건너기

dp(i, j, k) : 마지막으로 밝은 돌이 돌다리 k의 i번째돌이거나 그 이전 돌이고 두루마리의 j번째 문자열까지 처리한 경우의 수

dp(i, j, k) = dp(i-1, j, 1-k) + tmp, tmp = if 돌다리 k의 i번째 돌과 두루마리의 j번째 문자열이 같으면: dp(i-1, j-1, 1-k) else: 0

 

15912 우주선 만들기

dp(i) : 1~i까지 부품을 살 때 최소비용, E/W(i, j)를 i부터 j사이 E/W의 최대값이라 한다면

$dp(i) = \min\limits_{k}(dp(k) + W_{k+1, i}*E_{k+1, i}), 0 \leq k < i $

 

다만 구간의 최대값 부분은 세그트리를 이용하여 구했습니다.

시간은 $O(N^2log(N))$입니다.(N이 1,000)

 

21765 Opinion Pool

 

각 $S_{i}$에 대하여 $p*\left | S_{i} \right | $ 이상의 $S_{i}$의 구성원이 이슈에 찬성합니다

결국 M가지 셋에 대하여 $\max\limits_{i}\left ( \frac{\left | S_{i} \right | - 1}{\left | S_{i} \right |} \right )$ 를 찾아주면 문제를 해결 할 수 있습니다.

다만 이때 구성원이 여러 셋에 중복해서 들어 있을 수 있습니다.

따라서 모든 셋에 대해 탐색할 때 크기가 작은 셋부터 돌면서 중복을 체크해주어야 합니다

 

하지만 이 부분은 79brue님의 구현이 훨씬 더 간편하여 추가합니다

$X_{i}$ = i가 속한 셋의 최소 크기

위와 같이 정의한 이후 모든 i에 대해 가장 큰 $X_{i}$ 값을 찾아주면 쉽게 해결 할 수 있습니다

 

 

추가중...