[c++] 백준 16단계

알감자·2022년 4월 4일
C알고리즘정수론및조합론
0

백준알고리즘

목록 보기
16/52

#5086

#include <iostream>
using namespace std;

int main()
{
	int num1, num2;

	while (1)
	{
		cin >> num1 >> num2;

		if (num1 == 0)
			break;

		if ((num2 % num1) == 0) //num2가 num1으로 나누어진다면
		{
			cout << "factor" << "\n";
		}
		else if ((num1%num2) == 0)
		{
			cout << "multiple" << "\n";
		}
		else
		{
			cout << "neither" << "\n";
		}
	}

	return 0;
}

#1037

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int N;
	long long arr[51] = { 0 };
	long long result = 0;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	sort(arr, arr + N); //오름차순 정렬 

	//1. N의 개수가 짝수일 때 -> arr[0]과 arr[N-1]을 곱하기
	//2. N의 개수가 홀수일 때 -> arr[N/2]의 제곱

	if (N % 2 == 0) //N이 짝수라면
	{
		result = arr[0] * arr[N - 1];
	}
	else
	{
		result = arr[N / 2] * arr[N / 2];
	}
	
	cout << result;

	return 0;
}

#1934

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b)
{
	int c;

	while (b != 0)
	{
		c = a % b; //c에 a % b의 나머지를 저장
		a = b;
		b = c;
	}

	return a;
}

int main()
{
	int T, num1, num2, result;
	cin >> T;

	for (int i = 0; i < T; i++)
	{
		cin >> num1 >> num2;

		if (num1 >= num2)
		{
			result = (num1 * num2) / gcd(num1, num2);
		}
		else
		{
			result = (num1 * num2) / gcd(num2, num1);
		}

		cout << result << "\n";
	}

	return 0;
}

#2981

//너무 어려워서 구글링함,,

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int gcd(int a, int b)
{
	int c;

	while (b != 0)
	{
		c = a % b; //c에 a % b의 나머지를 저장
		a = b;
		b = c;
	}

	return a;
}

int main()
{
	int N;
	long long result;
	vector<long long> vec;
	long long arr[100] = { 0 };

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	sort(arr, arr + N);

	result = arr[1] - arr[0];
	for (int i = 2; i < N; i++)
	{
		result = gcd(result, arr[i] - arr[i - 1]);
	}

	for (int i = 2; i*i <= result; i++)
	{
		if ((result % i) == 0)
		{
			vec.push_back(i);
			vec.push_back(result / i); //i의 짝을 구하는 것
		}
	}

	vec.push_back(result);
	sort(vec.begin(), vec.end()); //오름차순으로 정렬

	//중복 제거
	vec.erase(unique(vec.begin(), vec.end()), vec.end()); 

	for (int i = 0; i < vec.size(); i++)
		cout << vec[i] << " ";

	return 0;
}

#3036

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b)
{
	int c;

	while (b != 0)
	{
		c = a % b; //c에 a % b의 나머지를 저장
		a = b;
		b = c;
	}

	return a;
}

int main()
{
	int N;
	int gcd_result = 0;
	int R[100] = { 0 };
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> R[i];
	}


	for (int i = 1; i < N; i++)
	{
		gcd_result = gcd(R[0], R[i]);
		if (R[0] == R[i])
		{
			cout << "1/1" << "\n";
		}
		else
		{
			cout << R[0] / gcd_result << "/" << R[i] / gcd_result << "\n";
		}
		
	}

	return 0;
}

#11050

#include <iostream>
#include <algorithm>
using namespace std;

int fac(int n)
{
	if (n == 0 || n == 1)
		return 1;

	return n * fac(n - 1);
}

int main()
{
	int N, K, result = 0;

	cin >> N >> K;

	result = fac(N) / (fac(K) * fac(N - K));

	cout << result;

	return 0;
}

#11051

//DP를 사용하여 풀기

#include <iostream>
#include <algorithm>
using namespace std;

long long DP[1001][1001] = { 0 };

int main()
{
	//점화식 : DP[N][K] = DP[N-1][K-1] + DP[N-1][K]

	int N, K;
	cin >> N >> K;

	DP[0][0] = 1;
	DP[1][0] = 1;
	DP[1][1] = 1;

	for (int i = 2; i <= N; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			if (j == 0)
				DP[i][j] = 1;
			else if (j == i)
				DP[i][j] = 1;
			else
				DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j]) % 10007;
		}
	}
	
	cout << DP[N][K];
	return 0;
}

#1010

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int T, N, M;
	cin >> T;

	for (int i = 0; i < T; i++)
	{
		cin >> N >> M;

		long long result = 1;
        int k=1;
        
		for (int j = M; j > M - N; j--)
		{
			result *= j;
            result /= k;
            k++
		}

		cout << result << "\n";
	}

	return 0;
}

#9375

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main()
{
	int T, N;
	string kind, name;
	cin >> T;

	for (int i = 0; i < T; i++)
	{
		cin >> N;
		map<string, int> m;
		int result = 1;

		for (int j = 0; j < N; j++)
		{
			cin >> name >> kind;

			if (m.find(kind) == m.end())
			{
				m.insert({ kind, 1 });
			}
			else
			{
				m[kind]++;
			}
		}

		for (auto num : m)
		{
			result *= (num.second + 1);
		}

		cout << result - 1 << "\n";
	}

	return 0;
}

// 참조 : https://donggoolosori.github.io/2020/10/05/boj-9375/


#1676

#include <iostream>
using namespace std;

int main()
{
	//N을 소인수분해 한 뒤 5의 개수를 세면 된다.

	int N, result = 0;
	cin >> N;

	result = N / 5 + N / 25 + N / 125;
	
	cout << result;
	
	return 0;
}

다른풀이

#include <iostream>
using namespace std;

int main()
{
	//N을 소인수분해 한 뒤 5의 개수를 세면 된다.

	int N, result = 0;
	cin >> N;

	for (int i = 5; i <= N; i *= 5)
	{
		result += (N / i);
	}

	cout << result;
	
	return 0;
}

#1676

//이렇게 풀었는데 틀렸다.. 

#include <iostream>
using namespace std;

int main()
{
	//result_1 : N! 중 5의 개수
	//result_2 : (N-M)! 중 5의 개수
	//result_3 : M! 중 5의 개수

	long long N, M, result =0;
	long long result_1 = 0, result_2 = 0, result_3 = 0;

	cin >> N >> M;

	for (int i = 5; i <= N; i *= 5)
	{
		result_1 += (N / i);
	}

	for (int i = 5; i <= N - M; i *= 5)
	{
		result_2 += ((N - M) / i);
	}

	for (int i = 5; i <= M; i *= 5)
	{
		result_3 += (M / i);
	}

	result = result_1 - result_2 - result_3;
	cout << result;

	return 0;
}

찾아보니까 2의 개수랑 5의 개수 중에 작은 것을 비교해서 구해야한다고 한다..

#include <iostream>
#include <algorithm>
using namespace std;

long long five_cnt(long long n)
{
	long long result = 0;

	for (long long i = 5; i <= n; i *= 5)
	{
		result += (n / i);
	}

	return result;
}

long long two_cnt(long long n)
{
	long long result = 0;

	for (long long i = 2; i <= n; i *= 2)
	{
		result += (n / i);
	}

	return result;
}

int main()
{
	//result_1 : N! - (N-M)! - M!  => 5로
	//result_2 : N! - (N-M)! - M!  => 2로

	long long N, M, result =0;
	long long result_1 = 0, result_2 = 0, result_3 = 0;

	cin >> N >> M;

	result_1 = five_cnt(N) - five_cnt(N - M) - five_cnt(M);
	result_2 = two_cnt(N) - two_cnt(N - M) - two_cnt(M);

	cout << min(result_1, result_2);

	return 0;
}
profile
알감자
이전 포스트

[c++] 백준 15단계

다음 포스트

[c++] 백준 18단계

0개의 댓글