7/27~7/28 연습

2017. 7. 29. 08:32알고리즘 문풀/BOJ 연습

어제 올리려고 하다가 9시에 자버렸다 ㅁㄴㅇㄹ...

이번에는 MWT 특집.


2011. 암호코드

문제 : icpc.me/2011


간단한 dp인데, 0인 경우를 생각해주지 않으면 가버릴 수 있다. 입력 문자열을 \(S\)라고 하고, \(D[i]\)를 \(S_1 \cdots S_{i-1} \)를 해석할 수 있는 경우의 수라고 두자. 입력이 0으로 시작하지 않는다는 것이 보장되어 있으므로 \(D[2]=1\)이다. 이제 dp를 앞에서 뒤로 뿌려주자.

\(S_i \neq 0\)인 경우, \(S_i\)를 하나의 암호문으로 해석할 수 있으므로 \(D[i+1]+=D[i]\).

\(S_i \neq 0 \wedge 10S_i + S_{i+1} < 27\)인 경우, \(S_iS_{i+1}\)를 하나의 암호문으로 해석할 수 있으므로 \(D[i+2]+=D[i]\).

최종 답은 \(D[n+1]\)이 된다.


Time Complexity : \(O(n)\).


3621. 족보

문제 : icpc.me/3621


ㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷ

간단한 수학적 귀납법으로, \(P(i)\)를 조상이 i명일 때 추가해야 하는 가짜 조상의 수라고 할 때, \(P(i)=P(i-d+1)+1\)이 성립함을 알 수 있다. 따라서 입력을 통해 \(x\)의 조상 수를 구해놓고, 0부터 \(n\)까지 \(P(parents(x))\)를 구해주면 된다. 아무생각없이 for문 0부터 \(n-1\)까지 돌리면 나처럼 MWT를 낼 수 있으니 주의하자....


Time complexity : \(O(n)\)


1766. 문제집

문제 : icpc.me/1766


나름 중요한 개념을 담고 있는 문제이다.

"위상 정렬 중 가장 priority가 작은 것을 구하여라!"라는 문제인데, 일반적인 DFS로 위상정렬을 할 경우에는 이를 고려해줄 수가 없다. (탐가네 빡대가리 X렢씨처럼 인접 리스트를 정렬해둔다고 해결할 수 있는 게 아니다) 이는 위상정렬의 클래-식한 버전과 priority_queue를 활용하여 해결할 수 있다.


입력으로부터 각 정점의 in-degree를 구해두자. in-degree가 0인 정점들을 pq에 넣는다. pq가 빌 때까지, top을 그래프에서 제거하면서 in-degree가 0이 되는 정점들을 계속 pq에 넣어주면 된다.


Time Complexity : \(O((V+E) lg V)\)


3825. 은행수

문제 : icpc.me/3825


그냥 가우스 소수 판별 문제인데, 내가 왜 이렇게 코드를 짰는지 이해할 수가 없다..... (정올 시작할 때쯤 틀린 문제)

가우스 정수 \(z=(x,y)\)에 대해 \(x^2 + y^2\)를 norm \(N(z)\)이라고 할 때, norm이 \(m^2+n^2\)보다 작은 가우스 정수를 모두 돌면서 norm이 \(m^2+n^2\)의 약수인 수가 5개 이상이면 C, 아니면 P를 출력하면 된다.


[증명]

페르마의 두 제곱수 정리의 확장판에 의해, 어떤 자연수 \(X\)가 \(4k+3\)꼴의 소인수를 짝수 개만 가질 경우 \(X\)는 두 자연수의 제곱합으로 나타낼 수 있다. 즉 \(N(Z)=X\)를 만족하는 가우스 정수 \(Z\)가 존재한다.

따라서 \(N(a)|N(b)\)일 경우, \(\frac{N(b)}{N(a)}\) 또한 모든 \(4k+3\)꼴의 소인수를 짝수개만 가지므로 어떤 가우스 정수의 norm이 될 수 있다. 가능한 a가 (가우스 자연수 범위에서)5개 이상일 경우 가우스 정수 b는 합성수이다.


Time Complexity : \(O(T(m^2+n^2))\)


[개선_8/4]

사실 시간복잡도를 더 줄일 수 있다. 어떤 가우스 정수 \(z\)가 합성수라면, \(1<N(w)<\sqrt{N(z)}\)인 가우스 정수 \(w\)가 존재한다. 따라서 기존의 norm bound인 \(m^2+n^2\)를 \(\sqrt{m^2+n^2}\)로 줄일 수 있다. 실행시간도 4ms에서 0ms로 줄었다!


Improved Time Complexity : \(O(T\sqrt{m^2+n^2})\)


아 어려운 것도 풀어야 하는데...

'알고리즘 문풀 > BOJ 연습' 카테고리의 다른 글

7/30 ~ 7/31 연습  (0) 2017.08.01
7/29 연습  (0) 2017.07.30
7/26 연습  (0) 2017.07.27
7/25 연습  (0) 2017.07.26
7/24 연습  (0) 2017.07.25