Doby's Lab

https://www.acmicpc.net/problem/12037 12037번: Polynesiaglot (Small1) In Case #1, suppose that the only vowel is a and the only consonant is h. Then the possible valid words of length 4 are: aaaa, aaha, ahaa, haaa, haha. In Case #2 (which would not appear in the Small dataset 1), suppose that the two vowels are a a www.acmicpc.net Solved By: DP cache[i][0]: 모음으로 끝나는 길이가 i인 문자열의 개수 cache[i][0]: 자음..

https://www.acmicpc.net/problem/11525 11525번: Farey Sequence Length Given a positive integer, N, the sequence of all fractions a / b with (0 < a  b), (1 < b  N) and a and b relatively prime, listed in increasing order, is called the Farey Sequence of order N. For example, the Farey Sequence of order 6 is: 0/1, 1/6, 1 www.acmicpc.net Solved By: Euler Phi Function 이번 문제를 풀면서 페리 수열에 대해 공부해봤습니다. (..

https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net Solved By: DP in Tree (공부한 풀이 출처: https://hqjang.tistory.com/104) 우선 이분법적으로 생각할 수 있습니다. 어떤 노드는 2가지 상태밖에 지니지 못 합니다. 1. 일반인인 경우 2. 얼리어답터인 경우 두 가지 경우에 대해서 생각해봅시다. [일반인인 경우] 어떤 노드가 일반인이라면 자식 노드들은 전부 얼리어답터여야 합..

https://www.acmicpc.net/problem/15312 15312번: 이름 궁합 영어 대문자 알파벳 26개의 획수는 순서대로 3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1 로 정한다. (출제자가 알파벳 대문자를 쓰는 방법이 기준이다) www.acmicpc.net Solved By: DP #include #include using namespace std; int base[26] = {3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1}; int main(){ string a, b; cin >> a >> b; vecto..

https://www.acmicpc.net/problem/19577 19577번: 수학은 재밌어 xφ(x) = n을 만족하는 양의 정수 x가 존재하면 최소의 x를, 존재하지 않으면 −1을 출력한다. www.acmicpc.net Solved By: Euler Phi Function xφ(x) = n에서 얻어낼 수 있는 정보는 x는 n의 약수라는 것입니다. 즉, n 이하의 모든 양의 정수를 탐색할 필요가 없다는 뜻입니다. n의 약수를 전부 얻어낼 수 있게 코드를 짭니다. 다음은 Euler Phi를 구현해야 하는데 이전 문제에서는 계속 폴라드 로를 사용해서 구현을 했었는데 소인수의 개수를 알 필요 없이 어떤 소인수만 가지는지 알면 되기 때문에 폴라드 로를 사용하지 않고 구해봅시다. (출처: https://ne..

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net Solved By: Sieve of Eratosthenes Sieve of Eratosthenes를 사용하되 체크하는 부분을 sqrt(MAX)까지만 해도 되는 것을 알고서 구현을 해줍니다. 그리고, 방문 배열을 사용하지 않는 코드를 짜서 문제를 풀어봅니다. 왜냐하면 Sieve of Eratosthenes에서 사용했던 num 배열을 다시 한 번 사용하여 n에서 어떤 소수를 뺀..

https://www.acmicpc.net/problem/13926 13926번: gcd(n, k) = 1 자연수 n이 주어졌을 때, gcd(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net Solved By: Pollard's Rho, Euler Phi Function 내 생각 Pollard's rho를 이용해 소인수 분해한 factor들을 구하고, 중복되는 것들은 없애서 1 ~ N까지의 수들을 탐색하며 factor로 나머지가 0으로 나뉘는 것이 있는지 탐색한다. ==> 시간 초과 N이 (1 > N; ull ans = N; if(N == 1){ cout

https://www.acmicpc.net/problem/10854 10854번: Divisions David is a young boy and he loves numbers. Recently he learned how to divide two numbers. David divides the whole day. He is happy if the result of the division is an integer, but he is not very amused if this is not the case. After quite a while he decide www.acmicpc.net Solved By: Pollard's Rho 문제를 읽어보면 알겠지만 이 문제는 N이 주어지면 N의 약수의 개수를 구하는 문..