1.배수와 약수
#include <iostream>
using namespace std;
int main()
{
int num1, num2;
cin >> num1 >> num2;
while (num1 != 0 && num2 != 0)
{
if (num2 % num1 == 0)
{
cout << "factor" << endl;
}
else if (num1 % num2 == 0)
{
cout << "multiple" << endl;
}
else
{
cout << "neither" << endl;
}
cin >> num1 >> num2;
}
}첫 번째 숫자가 두 번째 숫자의 약수이다.
첫 번째 숫자가 두 번째 숫자의 배수이다.
두가지 조건을 검사한다
첫번째 조건은 두번째 숫자를 첫번째 숫자로 나눴을때 나머지가 없는것으로 num2 % num1 == 이다.
두번쨰 조건은 첫번째 숫자를 두번쨰 숫자로 나눴을때 나머지가 0이므로 num1 % num2 == 0을 검사해주면 된다 둘다 아닌경우엔 neither를 출력한다.
2.약수
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n,ans;
int arr[50];
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
sort(arr, arr + n);
if (n == 1)
ans = arr[0] * arr[0];
else
ans = arr[0] * arr[n-1];
cout << ans << endl;
}약수들을 배열에 입력받은후 sort함수를 통해 정렬한다 다음 만약 하나가 입력되었다면 그수를 제곱하면 정답이고 아닐경우엔 처음과 마지막값을 곱해주면 정답을 알수있다.
3.최대공약수와 최소공배수
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
int c;
while (b != 0)
{
c = a % b;
a = b;
b = c;
}
return a;
}
int main()
{
int num1, num2;
cin >> num1 >> num2;
cout << gcd(num1, num2) << endl << num1 * num2 / gcd(num1, num2) << endl;
}gcd와 lcm 을 구하는 문제이다 유클리드 호재법을 이용한 알고리즘으로 gcd를 구한뒤 입력받은 수 num1 * num2에 gcd를 나눠주면 lcm을 알수있다.
4.최소공배수
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
int c;
while (b != 0)
{
c = a % b;
a = b;
b = c;
}
return a;
}
int main()
{
int num1, num2;
int cnt;
cin >> cnt;
while (cnt--)
{
cin >> num1 >> num2;
cout << num1 * num2 / gcd(num1, num2) << endl;
}
}2번문제에서 사용한 알고리즘을 그대로 사용하면 해결할수있다.
5.검문
#include <iostream>
#include <algorithm>
using namespace std;
int arr[100]; // 입력받는 배열
int ans[100]; // 최대공약수의 약수를 구하는 배열
int gcd(int a, int b) { // 최대공약수 구하는 함수
return a % b ? gcd(b, a%b) : b;
}
int main() {
//입력받기
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> arr[i];
sort(arr, arr + n); // 오름차순 정렬
//최대공약수 구하기, arr[i]-arr[i-1] = M * (arr[i]/M - arr[i-1]/M)
int sub = arr[1] - arr[0];
for (int i = 2; i < n; i++) sub = gcd(sub, arr[i] - arr[i - 1]);
//최대공약수의 약수 구하기
int count = 0;
for (int i = 1; i*i <= sub; i++) {
if (sub%i == 0) {
ans[count++] = i;
if (i != sub / i) ans[count++] = sub / i;
}
}
sort(ans, ans + count);
//출력
for (int i = 0; i < count; i++) {
if (ans[i] != 1) cout << ans[i] << " ";
}
}arr[N] - arr[N-1] = M * (arr[N] / M - arr[N-1] / M )
즉, 반복문을 돌려 arr[k] - arr[k-1]들의 최대 공약수를 구한다면, M을 구해 낼 수 있게 된다.
6.링
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
int c;
while (b != 0)
{
c = a % b;
a = b;
b = c;
}
return a;
}
int main(void)
{
int arr[100];
int cnt,m_num,s_num,gcd_num;
cin >> cnt;
for (int i = 0; i < cnt; i++)
{
cin >> arr[i];
}
m_num = arr[0];
for (int i = 1; i < cnt; i++)
{
gcd_num = gcd(m_num, arr[i]);
cout << m_num / gcd_num << '/' << arr[i] / gcd_num << endl;
}
}바퀴수는 한원의 반지름 / 다른원의 반지름으로 알수있을것이고 정답은 이를 약분한 값을 출력하는것이다 각 수를 두수의 최대공약수로 나눈값을 /를 사이에 두고 출력 하면된다.
7.이항계수1
#include <iostream>
using namespace std;
int factorial(int a)
{
if (a == 0)
return 1;
return (a * factorial(a - 1));
}
int main(void)
{
int n, k;
cin >> n >> k;
cout << factorial(n) / factorial(k) / factorial(n - k) << endl;
}수의 범위가 10으로 작기때문에
이항계수의 공식 N!/k!*(n-k)! 로 풀수있다.
8.이항 계수 2
#include <iostream>
using namespace std;
int dp[1001][1001] = { 0, };
int main(void)
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == j || j == 0)
{
dp[i][j] = 1;
}
else
dp[i][j] = (dp[i - 1][j - 1] + dp[i-1][j]) % 10007;
}
}
cout << dp[n][k] << endl;
}입력되는 수의 범위가 커 전문제와 같은 방식으로 해결할수없다 다른 이항계수 공식인
(N+1 K+1) = (N k) + (N k+1)을 dp를 통해 구현함으로써 해결할수있다.
9.다리놓기
#include <iostream>
using namespace std;
int main(void)
{
int n,m,cnt;
cin >> cnt;
while (cnt--)
{
int dp[30][30] = { 0, };
cin >> n >> m;
for (int i = 0; i <= m; i++)
{
dp[1][i] = i;
}
for (int i = 2; i <= n; i++)
{
for (int j = i; j <= m; j++)
{
for (int k = j; k >= i; k--)
{
dp[i][j] += dp[i - 1][k - 1];
}
}
}
cout << dp[n][m] << endl;
}
}다리를 놓는 문제이다 DP를 통해 해결할수있다 dp[3][3] 은 dp [2][2]+ dp [2][3] 과 같다 다리를 하나 고정해놓고 다른 다리를 놓는다고 가정한다고 생각하면 이해하기 편하다 위와같은 점화식을 반복문을 통해 구성해 답을 유추할수있다.
- 패션왕
#include <string>
#include <iostream>
#include <map>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int cnt;
cin >> cnt;
int n;
string catag, name;
while (cnt--)
{
map<string, int> m;
cin >> n;
while (n--)
{
cin >> name >> catag;
if (m.find(catag) == m.end())
{
m.insert({ catag, 1 });
}
else
m[catag]++;
}
int ans = 1;
for (auto i : m)
{
ans *= (i.second + 1);
}
ans -= 1;
cout << ans << '\n';
}
return 0;
}
문자열에관해 알아볼수있는 문제였다 공식은 간단하다 만약 N개의 안경과 M개의 옷이있다면 선택지는 (N+1) * (M+1) -1개이다 N개의 선택지에 벗는경우 하나를 더하고 곱해준후 모두 벗는 경우는 제외하라고 문제에 나와있기때문에 이를 빼주면 된다 공식은 간단하니 이를 코드로 구현하면 map을 사용했다 앞에는 문자열이 들어가고 뒤에는 그 문자열의 갯수가 들어간다 입력을 받으며 만약 이미 카탈로그에 있다면 갯수를 하나 늘려주고 아니라면 새로 추가한다 다음 반복문을통해 각각에 1을 더한 값을 곱해주고 1을빼준다.
11.팩토리얼 0의 갯수
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, temp, two = 0 , five = 0;
cin >> n;
for (int i = 2; i <= n; i++)
{
temp = i;
while (temp % 2 == 0)
{
temp /= 2;
two++;
}
temp = i;
while (temp % 5 == 0)
{
temp /= 5;
five++;
}
}
cout << min(two, five) << endl;
}단순 n값을 입력받아 재귀를 통해 팩토리얼을 구하고 10으로 나누며 0인지체크하기엔 시간초과가 뜬다 여기서우리는 팩토리얼의 값이 아니라 0의 갯수를 구하는것에 초점을 두어여한다.
0의 갯수라는 것은 수가 얼마가됬든 그수가 2,5를 얼마나 약수로 가지고있냐에 비례한다 다른 약수를 몇개를 가지고있든 2와 5 짝의 갯수에 따라 0의 갯수가 정해진다 즉 우리는 2와 5 두약수의 최솟값을 구해주면된다 대부분 5를 적게 가지기 때문에 5만 구하는 방법도 있지만 나는 두가지 모두 구하는 방법을 선택했다 N! 은 1부터 N까지 곱해지는것이기때문에 1부터 N까지 늘리면서 해당값이 몇개의 2를약수를 가지는지 더하면된다 이와같은 방법으로 5를 약수로 몇개 취하는지 구한후 2의 갯수와 min 연산을 통해 값을 구한다.
12.조합 0의 갯수
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef unsigned long long ull;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ull n, m;
cin >> n >> m;
ull count[2] = { 0, };
for (ull i = 2; i <= n; i *= 2)
{
count[0] += n / i;
}
for (ull i = 2; i <= n-m; i *= 2)
{
count[0] -= (n-m) / i;
}
for (ull i = 2; i <= m; i *= 2)
{
count[0] -= m / i;
}
for (ull i = 5; i <= n; i *= 5)
{
count[1] += n / i;
}
for (ull i = 5; i <= n - m; i *= 5)
{
count[1] -= (n - m) / i;
}
for (ull i = 5; i <= m; i *= 5)
{
count[1] -= m / i;
}
cout << min(count[0], count[1]) << endl;
return 0;
}위문제에서 팩토리얼이 아닌 조합공식을 사용하면(n k)는 n! / (n-k)! /k!이다 /는 그만큼 약수를 빼는것과 같다 그러므로 n의 2,5약수 갯수에서 n-k,k의 약수 갯수를 빼주면된다.
