4주차 연습 (1)

연습 (1) 에서는 solved.ac 기준 G5...G1 문제들을 다루고, 연습 (2)에서는 solved.ac 기준 P5...P3 문제들을 다룹니다.

https://www.acmicpc.net/problem/1885

1885번: 비부분수열

비고: 부분수열 $p$의 모든 원소도, $1$ 이상 $k$ 이하로 이루어져야 합니다.

 

풀이

$p$가 $S$의 부분수열이라면 $p$의 모든 문자는 차례로 $S$에 대응됩니다. 이를 판단하는 방법은, $p$와 $S$를 모두 앞에서부터 보면서 현재 보고 있는 $p$에 있는 수와 $S$에 있는 수가 같으면 $S$에 있는 해당하는 문자와 $p$에 있는 해당하는 문자가 대응된다고 체크를 해 주고, $p$와 $S$ 모두 다음 문자로 넘어가면 됩니다. 대응되지 않을 경우에는 $S$만 넘어갑니다. ($p$는 모든 문자가 대응되어야 합니다.)

 

이를 이용해서, 우리는 길이가 고정되었을 때, 최악의 $p$를 생각해 볼 수 있습니다. 최악의 $p$는 앞에서부터 보았을 때, 가장 나중에 나타나는 문자로 구성된 수열이라는 것을 알 수 있습니다. 이를 이용하면, 수열을 앞에서부터 쭉 보면서, $k$개의 문자중 가장 마지막에 나타나는 종류의 문자로 $p$의 첫 문자를 구성하고, 그 인덱스 이후부터 가장 마지막에 나타나는 종류의 문자로 $p$의 두 번째 문자를 구성하고... 등의 알고리즘을 생각할 수 있습니다.

 

그냥 알고리즘을 구현하면 $O(nk)$의 시간이 들 수 있으므로, 배열을 앞에서부터 보면서 현재 문자가 등장한 적이 있는지 체크를 해 주면 "모든 문자가 등장한 첫 위치"를 알 수 있습니다. 그 위치는 해당하는 종류의 문자가 가장 마지막에 등장하는 종류의 문자라는 것을 알 수 있습니다. 이렇게 $p$를 앞에서부터 그리디하게 정할 수 있고, 다음 문자를 더 이상 정하지 못할 때(문자열 $S$가 끝날 때), $S$에 포함되지 않는 $p$를 만들게 됩니다.

 

코드: https://www.acmicpc.net/source/share/6a826c89ba384583baa7ca027e17f2fc

 

https://www.acmicpc.net/problem/2976

2976번: NIKOLA

풀이

현재 발판에 있는 위치는 인덱스가 자유롭게 이동할 수 있지만, 이동해야하는 거리는 항상 증가합니다. 양의 방향으로 이동할 경우 전 단계보다 1칸 더 먼 거리로 점프해야하고, 음의 방향으로 이동할 경우 전 단계의 이동한 거리만큼 점프합니다.

 

다음과 같은 동적 계획법을 생각합시다. $D_{i, j}$는 가장 마지막에 점프한 거리가 $i$ 칸이고 현재 위치가 $j$임을 의미합니다. $D_{i, j}$는 가장 마지막 점프가 양의 방향인 경우 $D_{i-1, j-i}$에서 왔으며, 가장 마지막 점프가 음의 방향인 경우, $D_{i, j+i}$상태에서 왔습니다. 즉 $D_{i, j} = \min(D_{i-1, j-i}, D_{i, j+i}) + C_j $이며, 이를 $i$가 증가하는 순, $j$가 감소하는 순으로 구해주면 됩니다.

초기 조건은 $D_{0, 1} = 0, D_{0, *} = \infty$이며, 답은 $D_{*, N}$의 최솟값입니다.

 

코드: https://www.acmicpc.net/source/share/158fdc80535945b6806dff02392816f3

 

https://www.acmicpc.net/problem/8298

8298번: Coins

풀이

O를 $-1$, R을 $K$로 대체한 수열에서 구간의 합이 $0$인 구간 중에 가장 긴 구간을 찾는 문제입니다. 수열의 $i$번째 원소까지의 합을 $S_i$라고 하면, $S_L = S_R$의 의미는, $L$초과 $R$이하의 구간에 있는 수의 합이 $0$이라는 것입니다.

누적합을 구해 가면서 이전에 같은 수가 등장한 가장 처음 인덱스를 구하면, 그 인덱스와의 차이가 합이 $0$이 되는 구간의 길이입니다.

 

코드: https://www.acmicpc.net/source/share/a5ab335a4f3645ab8f4e93a13ecc2da7

 

https://www.acmicpc.net/problem/15910

15910번: 바나나나빠나나

풀이

아래에 Deterministic Finite Automata와 Transition Diagram이 있습니다. 이를 사용해서 문제를 해결 해 봅시다.

처음에 $S_0$에서 시작합니다. 문자열을 차례로 보면서 나타나는 문자를 따라 이동합니다. (해당하는 문자가 적혀있지 않을 경우 즉, 다음 상태가 없는 경우에는 올바른 유사 바나나 문자열이 아닙니다.) 최종적으로 $S_6$에 도착한 후 문자열이 끝나면 해당 문자열은 올바른 유사바나나 문자열입니다.

 

우리는 이를 통해서 간단한 동적계획법을 생각해 볼 수 있습니다. $D_{i, j}$가 $i$번째 문자까지의 문자열을 상태 $j$로 만들기 위한 문자를 바꾸는 횟수(비용)이라고 생각합시다. 이렇게 하면 이미 $S$에 있는 문자를 가지고 상태를 전이할 때는 비용 없이, $S$에 있는 문자가 아니라면 비용을 $1$ 지불하고 상태를 전이한다고 생각하면 됩니다.

복잡하지만 식으로도 작성해 보면, $D_{i, j} = \min_{k \overset{c}{\rightarrow} j} (D_{i-1, k} + I_{c \ne S_i})$ 입니다. 여기서 $k \overset{c}{\rightarrow} j$는 상태 $k$에서 상태 $j$로 바꾸기 위한 문자는 $c$라는 뜻이고, $I_{c \ne S_i}$는 $c \ne S_i$이면 $1$, 아니면 $0$인 함수입니다. 초기상태는 $D_{0, 0} = 0, D_{0, *} = \infty$이고, 답은 $D_{N, 6}$입니다.

 

코드: https://www.acmicpc.net/source/share/6b14e2bb805b4c6fa1dcd42380120dfd

 

https://www.acmicpc.net/problem/13003

13003번: 배수열

풀이

$D_{l, n}$을 길이가 $l$이고 마지막 원소가 $n$인 수열의 개수라고 합시다. 초깃값은 $D_{0, 1} = 1, D_{0, *} = \infty$이고 이는 가장 처음에 아무 원소나 올 수 있다. 즉, 다음에 올 수는 $1$의 배수이다라는 의미입니다. 길이가 $l$이고 마지막 원소가 $n$인 수열에 마지막 원소를 추가하면, 길이가 $l+1$이고 마지막 원소가 $n, 2n, 3n, \cdots$인 수열을 만들 수 있습니다. 그래서 우리는 $D_{l+1, m} = \sum_{n \mid m} D_{l, n}$과 같은 매우 직관적인 수식을 쓸 수 있습니다. 이 수식을 구현해 주는게 전부입니다. 이제, 왜 이 풀이가 동작하는지 확인 해 봅시다.

 

우선, 구현을 정확히 $m, n$이 배수-약수 관계인 경우에만 $D$를 더해줬다고 합시다. 이는 $n$을 정하고 $m$을 $n$의 배수로 잡은 후에 $D_{l, n}$값을 $D_{l+1, m}$에 뿌려주는 방식으로 구현할 수 있습니다. 이 경우, $(m, n)$의 개수는 $O(N \log N)$입니다. 이 과정을 $l$번 하면 총 시간복잡도는 $O(N^2 \log N)$이 되어서, 시간 안에 충분히 계산할 수 있습니다.

 

$(m, n)$의 개수를 세어 봅시다. $n$을 고정시키면, 해당하는 $m$의 개수는 $\left \lfloor \frac{N}{n} \right \rfloor$입니다. $n$은 $1$ 이상 $N$ 이하의 수가 가능하기 때문에, 결국 $(m, n)$ 쌍의 수는 $\sum_{i = 1}^{N} \left \lfloor \frac{N}{i} \right \rfloor$입니다. 이 식을 정리 해 보면 $\sum_{i = 1}^{N} \left \lfloor \frac{N}{i} \right \rfloor \le \sum_{i = 1}^{N} \frac{N}{i} = N\left(\sum_{i = 1}^{N} \frac{1}{i}\right)$과 같이 됩니다.

여기서, $\sum_{i = 1}^{N} \frac{1}{i}$이 $O(\log N)$이기 때문에, 총 $(m, n)$ 쌍의 수는 $O(\log N)$입니다.

 

$\sum_{i = 1}^{N} \frac{1}{i}$이 $O(\log N)$인 설명은 매우 여럿이 있습니다. 다음 설명 중 하나를 참고하면 될 것 같습니다.

 

설명 1:

$\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} + \cdots \frac{1}{N} = (\frac{1}{1}) + (\frac{1}{2} + \frac{1}{3}) + (\frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7}) + (\frac{1}{8} + \cdots + \frac{1}{15}) + \cdots \frac{1}{N}$ 입니다. 여기서 괄호로 묶인 곳은 항상 $1$ 이하입니다. 왜냐하면 $i$번째 괄호 안에는 $\frac{1}{2^{i-1}}$부터 $\frac{1}{2^i-1}$까지의 수가 있고 이 괄호 안에는 $2^{i-1}$개의 수가 있으며, 괄호 안에 있는 모든 수는 $\frac{1}{2^{i-1}}$이하 이기 때문입니다. 즉, 괄호 안의 모든 수의 합은 $2^{i-1} \times \frac{1}{2^{i-1}} = 1$ 이하입니다.

괄호 안에 있는 수의 개수는 $2$배씩 늘어나므로, $N$까지 괄호에 포함시키기 위해서는 괄호가 $O(\log_2 N)$개 필요합니다.

 

설명 2:

$\sum_{i = 1}^{N} \frac{1}{i}$는 $\int_{i=1}^N \frac{1}{i} di$로 근사할 수 있으며, 이는 $\ln i |_{1}^{N} = \ln N$ 입니다. 즉, $\sum_{i = 1}^{N} \frac{1}{i}$는 $O(\log N)$입니다.

 

코드: https://www.acmicpc.net/source/share/ccda21a16ac548b596f6b933a15b9513

 

https://www.acmicpc.net/problem/3142

3142번: 즐거운 삶을 위한 노력

풀이

어떤 수가 완전제곱수라는 것은 어떤 수를 소인수분해 했을 때 모든 지수가 다 짝수라는 것과 동치입니다. 또한, 소인수분해가 된 두 수를 곱하는 것은 모든 지수를 더해주는 것과 같습니다.

이 둘을 이용하면 결국 들어오는 수를 소인수분해 해주고 각 소인수 별로 개수를 세어줘서 모든 소인수에 대해 해당 소인수가 짝수개 있는지를 확인하면 됩니다. $M$이 최댓값일 경우, $O(N \sqrt M)$ 정도의 시간복잡도를 가지게 됩니다. 하지만 이것은 이 문제를 푸는 데에 충분하지 않습니다.

 

빠르게 소인수분해를 해 봅시다. 소수 판정을 하는 에라토스테네스의 체를 생각 해 보면, 어떤 수가 소수일 경우에는 자기의 모든 배수를 소수가 아니라고 표시하게 됩니다. 합성수에 대해서, 자기를 소수가 아니라고 체크한 수가 어떤 수인지 저장하는 것으로 소인수를 하나 알 수 있습니다. 이렇게 수를 소인수로 계속 나눠보는 것으로 소인수분해를 할 수 있습니다. 시간복잡도는 에라토스테네스 체의 시간복잡도인 $O(M \log \log M)$과 이후 소인수분해의 시간복잡도인 $O(N \log M)$을 합친 $O(N \log M + M \log \log M)$입니다.

 

코드: https://www.acmicpc.net/source/share/70e2a6df35b84f34b07283a0e4250a35

 

https://www.acmicpc.net/problem/2245

2245번: 배열 정리하기

풀이

$3$번 이상 등장하는 수가 있으면 비둘기집의 원리에 의해 $A$ 혹은 $B$에는 해당 수가 $2$번 이상 등장하게 되기 때문에 배열을 정리할 수 있습니다. 즉, 모든 수가 정확히 $2$번 등장하는 경우를 생각하면 됩니다.

 

같은 수가 등장하는 두 위치를 간선으로 이어준다고 생각하면, 사이클 여러개로 분할됩니다. (모든 정점의 차수가 2입니다.) 그래서, 해당 사이클을 하나에 대해서 정리를 해 준다고 생각합니다.

사이클에서 하나의 위치를 잡아서 방향을 정하면 (바꾸거나 바꾸지 않으면), 간선에 직접 연결된 위치의 방향도 정해집니다. 왜냐하면 같은 수가 속한 배열이 달라야 하기 때문에, 해당 수가 $A$, $B$ 배열중 어디에 존재하냐에 따라 해당 위치에서 수를 뒤집을지 아닐지 정해집니다. 이 방식을 이용하면, 사이클에 있는 모든 수의 방향은 정해집니다.

하나의 위치를 잡아서 정할 수 있는 방향이 $2$가지가 있기 때문에, 그 $2$가지 중에 최솟값을 잡아서 모든 사이클에 대해서 합을 구해주면 그것이 답이 됩니다.

이 방식으로 무조건 배열을 정리할 수 있음을 보이고, 구현의 편의를 위해 한 가지 성질을 더 찾아보겠습니다.

 

• 위 방식으로 배열을 정리할 수 있다.
  • 사이클을 차례대로 돌아가면서 방향을 정해줬을 때 최종적으로 마지막 두 원소는 항상 서로 다른 위치에 존재합니다. 왜냐하면, 모든 다른 수가 $A$ 배열과 $B$ 배열의 각각 한 자리를 차지하고 있기 때문에, 마지막 원소가 들어갈 자리가 $A$, $B$ 배열의 각각 한 자리밖에 존재하지 않습니다.
• $2$가지 방법에서 바꾸는 횟수의 합은 사이클의 길이이다.
  • 어떤 한 방향으로 정리가 가능하면, 배열의 모든 위치를 한 번 더 바꿨을 때, $A$하고 $B$가 바뀌게 되고 이 역시 정리된 결과입니다. 결국, 원래 바꿨던 원소를 바꾸지 않고 원래 바꾸지 않았던 원소를 바꾸는는 것으로도 배열을 정리할 수 있으므로, 두 방법의 횟수 합은 사이클의 길이입니다. (사이클의 모든 위치가 두 방법에서 정확히 한 방법에서 두 수를 바꾸게 됩니다.)

 

코드: https://www.acmicpc.net/source/share/d8f05c6eb879468b8b5cf868ac7625e6​