문제 https://www.acmicpc.net/problem/7806 풀이 처음에는 n!을 기준으로 gcd(n,k) , gcd(n-1,k / gcd(n,k)) 이런 식으로 최대공약수를 구해나가려고 했습니다. 이런 식으로 구현하게 되면 시간초과가 발생합니다. 이 문제의 경우에는 K를 기준으로 소인수분해하고 해당 소수가 n!에 몇 개 존재하는 지 찾아내서 지수가 작은 수를 통해 최대공약수를 구하는 방식으로 구현해야 합니다. n! 을 소인수분해 할 때 일반적으로 사용되는 것처럼 소수로 계속 나누게 되면 엄청난 시간이 걸립니다. n! 을 소인수분해 할 때는 n / 소수^1 + n / 소수^2 + n / 소수^3 ... 하시면 n! 을 소인수분해 했을 때 소수 갯수를 구할 수 있습니다. 소스코드 #include..
문제 https://www.acmicpc.net/problem/14476 풀이 문제풀이를 완전탐색 알고리즘으로 생각을 해보면 1~N까지의 수를 하나씩 다 빼보고 그 중에 가장 큰 최대공약수를 가질 수 있는 수를 빼는 것입니다. 하지만 완전탐색의 경우 1~N까지 숫자를 빼는 것과 숫자를 뺀 나머지 수들의 최대공약수를 구하는 과정에 있어서 시간초과가 발생할 것이라고 생각 했습니다. 제 풀이는 1부터 N까지 모두 빼보는 것까지는 완전탐색과 똑같은 방법입니다. 다른 점은 Segement Tree 를 이용해서 1~N까지의 최대공약수를 미리 저장해놓는 것입니다. 현재 숫자를 빼고 Segement Tree를 Update 해주고 비교해주는 거라고 보시면 됩니다. 소스코드 #include #include using na..
문제 https://www.acmicpc.net/problem/6569 풀이 큰 직사각형의 상태를 0(빈 칸), 1(채운 칸) 으로 경우의 수를 계산해나갔습니다. 현재칸이 blockNum 일 때 너비 w만큼의 칸을 상태를 저장해놓고 상태에 따라 가능한 직사각형을 채운다고 생각하시면 됩니다. 예를 들어, 높이가 3 너비가 5이면 직사각형의 번호는 아래와 같습니다. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0번째 칸에 높이 1, 너비 2 인 직사각형을 놓을 경우면 상태를 00011(10진수 3) 으로 표현하다고 생각하시면 됩니다. 소스코드 #include #include using namespace std; const int MAX_N = 11; long long gCache[(MAX_..