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})\)
아 어려운 것도 풀어야 하는데...