📝11050번: 이항 계수 1
문제 설명
이항 계수 1
해결 방법
이항계수를 구하는 문제로 N! / (K! * (N - K)!)을 구한다.
💻소스코드
#include <iostream>
using namespace std;
int main()
{
// 이항계수 1
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, K;
int a = 1, b = 1;
cin >> N >> K;
for (int i = 1; i <= K; i++)
b *= i;
for (int i = N; i > N - K; i--)
a *= i;
cout << a / b << '\n';
}📝11051번: 이항 계수 2
문제 설명
이항 계수 2
해결 방법
파스칼의 삼각형을 떠올리며 점화식을 사용, 파스칼의 삼각형을 이차원 배열로 간주한다. 동적 계획법을 적용하였다.
💻소스코드
#include <iostream>
using namespace std;
int main()
{
// 이항 계수 2
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// 파스칼의 삼각형, 동적 계획법으로 풀이
long long dp[1001][1001] = { 0, };
int N, K;
cin >> N >> K;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= N; j++) {
if (j == 0 || j == i) // 파스칼의 삼각형의 두 변은 모두 1
dp[i][j] = 1;
else
dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % 10007;
}
}
cout << dp[N][K] << '\n';
return 0;
}📝1010번: 다리 놓기
문제 설명
다리 놓기
해결 방법
다리를 놓을 수 있는 조합의 수를 구하면 된다. 강 서쪽의 사이트가 N개, 강 동쪽의 사이트가 M가 이므로 C(M, N)을 구한다.
💻소스코드
#include <iostream>
using namespace std;
int main()
{
// 다리 놓기
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T, N, M;
cin >> T;
for (int i = 0; i < T; i++) {
cin >> N >> M;
long long a = 1, b = 1;
// C(M, N)
for (int k = M; k > M - N; k--) {
a *= k;
a /= b;
b++;
}
cout << a << '\n';
}
return 0;
}📝9375번: 패션왕 신해빈
문제 설명
패션왕 신해빈
해결 방법
의상의 종류는 중복을 허용하지 않으므로 map을 이용한다. 의상의 종류를 map에 넣고 개수를 카운트한다. 모든 경우의 수를 세야 하므로 각 의상의 종류에 해당하는 개수 + 1(= 해당 의상 종류를 착용하지 않는 경우) 을 전부 곱한다. 맨 몸인 경우의 수 1을 뺀다.
💻소스코드
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main(void)
{
// 패션왕 신해빈
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T, n;
cin >> T;
for (int i = 0; i < T; i++) {
string dress, type;
int cnt = 1;
cin >> n;
map<string, int> dress_map;
for (int j = 0; j < n; j++) {
// dress는 중복되지 않으므로 입력만하고 사용하지 않음
cin >> dress >> type;
// map에 해당 type이 없으면 삽입, 있으면 value 증가
if (dress_map.find(type) == dress_map.end())
dress_map.insert({type, 1});
else
dress_map[type]++;
}
// map의 value + 1을 전부 곱함
for (auto d : dress_map)
cnt = cnt * (d.second + 1);
// 맨 몸인 경우의 수를 빼고 출력
cout << cnt - 1 << '\n';
}
return 0;
}📝1676번: 팩토리얼 0의 개수
문제 설명
팩토리얼 0의 개수
해결 방법
끝자리 0의 개수를 세기 위해서는 2와 5의 한 쌍이 몇개인지 세면 된다. 2의 개수는 5의 개수보다 항상 많을 것이므로 실질적으로 5의 개수만 카운트해주면 끝자리 0의 개수를 알 수 있다.
💻소스코드
#include <iostream>
using namespace std;
int main()
{
// 팩토리얼 0의 개수
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
int cnt = 0;
cin >> N;
// 0을 만드는 요소는 소인수 2와 5로 이루어진다.
// 2와 5가 곱해져야 0이 한 개 만들어지므로 곱해지는 5의 갯수만 카운트한다.
for (int i = 1; i <= N; i++) {
if (i % 5 == 0)
cnt++;
if (i % 25 == 0) // 5가 2개 포함됨.
cnt++;
if (i % 125 == 0) // 5가 3개 포함됨.
cnt++;
}
cout << cnt << "\n";
return 0;
}😖📝2004번: 조합 0의 개수
문제 설명
조합 0의 개수
해결 방법
끝자리 0의 개수를 세기 위해서는 2와 5의 한 쌍이 몇개인지 세면 된다.
조합 공식 nCm = n! / (m! * (n - m)!)
분자, 분모를 소인수분해 하였을 때 분자의 2의 개수에서 분모의 2의 개수를 뺀 값과 분자의 5의 개수에서 분모의 5의 개수를 뺀 값 중 더 작은 값을 구하면 해결할 수 있는 문제다. 팩토리얼 구성요소의 2의 개수와 5의 개수를 일일이 확인하는 것은 무조건 시간초과가 날 것 같아서 팩토리얼에서 어떤 숫자 k(이 문제에서는 2, 5)의 지수의 개수를 구하는 방법을 사용하였다.ex) N은 25, k는 2인 경우 25 / 2 = 12 (2, 4, 6, ... , 24) 25 / 4 = 6 (4, 8, 12, 16, 20, 24) 25 / 8 = 3 (8, 16, 24) 25 / 16 = 1 (16) 25! 에서 2의 개수는 22개 ex) N은 25, k는 5인 경우 25 / 5 = 5 (5, 10, 15, 20, 25) 25 / 25 = 1 (25) 25! 에서 5의 개수는 6개하지만 여기서 무심코 int형을 사용했다가 시간초과가 아니라 integer overflow를 마주쳐서 unsigned long long을 사용했다.
💻소스코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cnt(int k, int n) { // k는 k!, n은 팩토리얼 안의 개수를 구하고자 하는 숫자
int num = 0;
for (unsigned long long i = n; i <= k; i *= n)
num += k / i;
return num;
}
int main()
{
// 조합 0의 개수
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
int cnt_five = 0, cnt_two = 0;
cin >> n >> m;
// 조합공식: nCm = n! / (m! * (n - m)!)
cnt_two = cnt(n, 2) - cnt(n - m, 2) - cnt(m, 2); // 분자의 2의 개수에서 분모의 2의 개수를 뺌
cnt_five = cnt(n, 5) - cnt(n - m, 5) - cnt(m, 5); // 분자의 5의 개수에서 분모의 5의 개수를 뺌
cout << min(cnt_five, cnt_two) << '\n'; // 두 값 중 더 작은 값을 출력
}