BOJ 수학 1676 1049 1094 11051 C++

1676 팩토리얼 0의 개수

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

int n, m;

/*
2와 5를 곱할 때만 0이 생긴다
5보다 2가 많으니까 5만 세면 된다
근데 5의 배수가 예외
5*2=10
5*5*2*2=100
5*5*5*2^3=1000
2는 충분히 많다고 칠 수 있으므로(소인수분해 하면 2가 잔뜩나온다)
5의 배수는 1개씩 늘 때마다 0의 개수가 1개씩 증가되며 추가된다고 볼 수 있다
5^4=625는 문제 범위인 500을 넘으므로 패스
*/

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	while (n >= 2) {
		if (n % 5 == 0) m++;
		if (n % 25 == 0) m++;
		if (n % 125 == 0) m++;
		n--;
	}
	cout << m;
}

 

1049 기타줄

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

int n, m;
int set = 1001, one = 1001;

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n >> m;
	for (int i = 0;i < m;i++) {
		int a, b;
		cin >> a >> b;
		set = min(set, a);
		one = min(one, b);
	}

	int ans = 0;
	if (set < one * 6) ans += set * (n / 6); //6개 세트가 이득
	else ans += one * (n / 6) * 6; //낱개가 이득
	n %= 6;

	//6배수 빼고 나머지 잉여를 세트 하나로 퉁 칠 것인지 아니면 낱개 살 것인지
	if (set > one * n) ans += one * n; //낱개
	else ans += set; //세트 하나

	cout << ans;
}

 

1094 막대기

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

int n, m;

/*
문제가 잘 이해가 안 되는데..
64, 32, 16, 8, 4, 2, 1, 1을 가지고 X를 만든다는 이야기 같다
*/

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int x;
	cin >> x;
	int num[] = { 64, 32, 16, 8, 4, 2, 1, 1 };
	int sum = 0, res = 0;

	for (int i = 0;i < 8;i++) {
		if (sum + num[i] <= x) {
			sum += num[i];
			res++;
		}
	}
	if (sum == x) {
		cout << res;		
	}
}

 

11051 이항 계수2

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

int dp[1001][1001];

/*
이항계수 (n k) = nCk = n!/(n-k)!k! (0<=k<=n) 이다
점화식으로는
(n k) = (n-1, k) + (n-1, k-1)   | 0<k<n
      =  1                      | n==k or k=0

이유:
원소가 {1,2,3,4}가 있을 때 3개 뽑는 상황은 4C3
원소 1을 기준으로 보면
-원소 1을 선택: 나머지 3개 중 2개 선택 3C2
-원소 1을 선택 안 함: 나머지 3개 중 3개 선택 3C3
각 경우를 더한 결과가 4C3의 모든 경우
4C3=3C2+3C3 점화식과 같음

DP로 구현한다
중복 부분문제-중복되는 함수 호출
최적 부분구조-각 부분문제의 최적값이 전체 문제의 최적값
둘 다 만족하므로 DP 문제
*/

int go(int n, int k) {
	if (n == k || k == 0) return 1;

	if (dp[n][k] == 0) dp[n][k] = go(n - 1, k) % 10007 + go(n - 1, k - 1) % 10007;
	return dp[n][k];
}
//메모이제이션 안 쓰면 시간 초과

//int go(int n, int k) {
//	for (int i = 0;i < n;i++) {
//		for (int j = 0;j <= min(k, i);j++) {
//			if (i == j || j == 0) {
//				dp[i][j] = 1;
//			}
//			else dp[i][j] = dp[i - 1][j]%10007 + dp[i - 1][j - 1]%10007;
//		}
//	}
//	return dp[n][k];
//}
//이건 왠지 안 된다 확인 필요

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int x, k;
	cin >> x >> k;
	cout << go(x, k)%10007;
}

 

 

https://github.com/proqk/Algorithm/blob/ceff29fd17011e371fbafdf0726f295317332379/math/11051%20%EC%9D%B4%ED%95%AD%EA%B3%84%EC%88%982.cpp

GitHub - proqk/Algorithm: BOJ problem solving https://www.acmicpc.net/user/proqk & https://foxtrotin.tistory.com/