궤도

문제 풀이 myunji.tistory.com/231?category=1154147 [백준] 1676번 : 팩토리얼 0의 개수 문제 풀이 저 문제 기준으로 10은 1이다. 100은 2고, 1000은 3이다. 즉 해당 팩토리얼을 계산했을 때 10이 몇번이나 곱해졌는지 세어보면 답이 나올 것이다. 10=2x5다. 그니까 팩토리얼을 계산했을 때 myunji.tistory.com 이 문제의 풀이를 거의 그대로 사용할 것이다. nCm = n!/(m!(n-m)!)이다. 그니까 n!과 m!, 그리고 (n-m)!의 2와 5의 수를 각각 구한 뒤, 나눗셈 곱셈을 잘 고려해 계산하면 되겠다. 소스코드 #include #include using namespace std; pair binomial(long long n) { i..

문제 풀이 저 문제 기준으로 10은 1이다. 100은 2고, 1000은 3이다. 즉 해당 팩토리얼을 계산했을 때 10이 몇번이나 곱해졌는지 세어보면 답이 나올 것이다. 10=2x5다. 그니까 팩토리얼을 계산했을 때 곱해진 2의 수와 5의 수를 각각 구해 그 중 작은 것을 택하면 된다. 소스코드 #include #include using namespace std; int fact(int N) { int two_cnt = 0, five_cnt = 0; for (int i = 2; i N; cout

문제 풀이 문제 자체는 아주 쉬운 경우의 수 문제다. X, Y 종류의 의상이 있다고 하자. 각 종류별 의상은 이러하다. X - a, b Y - c X 종류의 의상에 대해 선택할 수 있는 경우는 {입지 않음, a, b}이고, Y 종류의 의상에 대해 선택할 수 있는 경우는 {입지 않음, c}이다. 둘다 입지 않을 수는 없으니 3x2-1=5가 선택할 수 있는 총 경우의 수이다. 입력을 잘 처리해서 정리하는게 거의 다인 문제인거다. 소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; struct outfit { //옷 정보 저장 string name; string kind; }; struct kindCnt { //종류별 옷의 개..

문제 풀이 myunji.tistory.com/228 [백준] 11050번 : 이항 계수 1 문제 본문 설마 이항 계수를 모르는 사람이 이 글을 보진 않겠지...고등학교 때 배우는 그거다. nCk를 구하면 되는건데 다들 알다시피 공식은 n!/(k!(n-k)!)이다. 이걸 그대로 코드로 작성하면 된다. myunji.tistory.com 이걸 동적 계획법으로 푸는 문제이다. 아마 학교에서 이항 계수에 대해 배웠을 때 파스칼의 삼각형도 들어봤을 것이다. nCk = n-1Ck-1 + n-1Ck 라는 공식을 기억하고 있다면 어렵지 않다. 소스코드 #include using namespace std; int dp[1001][1001] = { 0, }; int binomial(int N, int K) { if (N /..

문제 본문 설마 이항 계수를 모르는 사람이 이 글을 보진 않겠지...고등학교 때 배우는 그거다. nCk를 구하면 되는건데 다들 알다시피 공식은 n!/(k!(n-k)!)이다. 이걸 그대로 코드로 작성하면 된다. 소스코드 #include using namespace std; int binomial(int N, int K) { int m = 1, c = 1; int temp_N = N; int temp_K = K; if (N / 2 < K) { //5C3 같은 경우 K = N - K; temp_K = K; } for (int i = 0; i < K; i++) { m *= temp_N; c *= temp_K; temp_N--; temp_K--; } return m / c; } int main() { int N,..

문제 본문 입력 A, B, C가 있다고 하자. 이 수들을 M으로 나눴을 때의 나머지가 전부 같으니 이를 r이라고 하자. 그리고 입력된 수를 M으로 나눴을 때의 몫을 각각 x, y, z라고 하자. 별로 중요하진 않은 애들이다. 정리하면 A = M*x + r B = M*y + r C = M*z + r 이 된다. 여기서 A-B와 B-C를 해보겠다. A-B = M(w-x) B-C = M(x-y) 편의상 (w-x)를 k로 (x-y)를 l로 놓으면 A-B = Mk, B-C = Ml이 된다. 그니까 M은 (A-B)와 (B-C)의 공약수라는 것이다. 이걸 일반화하면 N개의 숫자가 있는 집합 X로 만들 수 있는 모든 K(K=A-B, A∈B∈X, A≠B)의 공약수가 M이 된다는 것이다. 쉽게 풀어쓰면 집합 X에서 숫자 2..

문제 풀이 주어진 두 수의 최소공배수를 구하는 문제이다. 설마 이 글을 보는 사람 중에 최소공배수를 모르는 사람이 있을 것이라고 생각하진 않는다. 혹시 두 수 A, B와 그들의 최소공배수 X, 최대공약수 Y가 있을 때 이들의 관계를 기억할지 모르겠다만... A*B = X*Y 이다. 초등학교인가 중학교인가에서 배우는 것이니 왜 이렇게 되는 거냐고 묻지 않았으면 좋겠다. 아무튼 내가 하고 싶은 말은 최소공배수를 구하는 문제는 그냥 최대공약수를 구하는 문제와 같다는 것이다. 그럼 최대공약수를 구하는 알고리즘은 어떻게 짜면 좋을까? A=1 ; i--)의 for문을 돌며 처음으로 A%i == 0 && B%i == 0가 되는 i 찾기 2. for(int i=A ; i>=1 ; i/=2)의 for문을 돌며 처음으로 ..