BOJ 수학 10610 1780 1292 2004 C++

10610 30

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


/*
"길거리에서 찾은 수에 포함된 숫자들을 섞어,
30의 배수가 되는 가장 큰 수를 만든다"

처음에 문제를 봤을 때는 주어진 N값을 소인수분해해서 나온 여러 숫자들을
어케 잘 연산해서 30의 배수를 만드는 줄 알았다.
그런데 무한히 더해버리면 무한히 큰 30의 배수를 만들 수 있기 때문에 이건 아니었다

예제를 다시 보니까 "포함된 숫자"라는 의미가
주어진 N의 각각 자리수를 의미하는 것이었다
그리고 각 자리수를 어케 잘 재배치해서 가장 큰 30의 배수를 만들면 된다

30의 배수가 될 조건을 만족하는지 확인하고
각 자리수를 큰 수부터 재배치한다

30의 배수가 될 조건
1. 끝자리가 0
2. 모든 자리의 수를 더하면 3의 배수
*/

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

	vector<int> v;
	long long sum = 0;
	for (int i = 0;i < s.size();i++) {
		int now = s[i] - '0';
		v.push_back(now);
		sum += now;
	}
	sort(v.begin(), v.end());
	if (v[0] != 0 || sum % 3 != 0) cout << -1;
	else {
		for (int i = v.size() - 1;i >= 0;i--) cout << v[i];
	}
	
}

 

 

1780 수들의 합

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

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

	long long sum = 0;
	int num = 1;
	int res = 0;
	
	while (sum <= n) {
		sum += num;
		res++;
		num++;
	}
	cout << res - 1; 

	//-1하는 이유. 합이 S를 넘기면 마지막 숫자를 뺀다
}

 

1292 쉽게 푸는 문제

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

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int a, b;
	cin >> a >> b;
	vector<int> v;
	for (int i = 1;i <= b;i++) {
		for (int j = 0;j < i;j++) {
			v.push_back(i);
		}
	}

	long long sum = 0;
	for (int i = a-1;i <= b-1;i++) {
		sum += v[i];
	}
	cout << sum;
}

 

2004 조합0의개수

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

/*
(n m)은 n! / (n-m)!m!

0의 개수=2와 5의 개수를 센다

이전에 풀었던 이항 계수 문제에서
f(n-1, m-1) + f(n-1, m)
1 -> n==m or m==0
이런 점화식을 썼으니까, 이번에도 이걸 사용해서 구하면서
2,5를 계산하나.. 그렇게 접근했는데
답이 안 나와서 살짝 검색하니 아무도 이렇게 하지 않았다..

더 쉬운 방법이 있더라
n!과 (n-m)!와 m!의 2의 배수의 개수, 5의 배수의 개수를 구하고
분모와 분자에 둘 다 같은 수가 있으면 사라지므로
n!에서 나온 개수에서 (n-m)!과 m!에서 나온 개수를 빼주면 된다
이걸 2와 5에 대해서 한다
그리고 둘 중 더 작은 값이 정답
왜 min이냐면 10이 만들어져야 하는데 2나 5 중 한 쪽이 아무리 많더라도
적은 쪽 개수만큼밖에 못 만들기 때문이다

범위가 크므로 long long을 사용한다
*/
long long n, m;
long long div5(long long n) {
	long long cnt = 0;
	for (long long i = 5; i <= n; i *= 5) {
		cnt += n / i;
	}
	return cnt;
}

long long div2(long long n) {
	long long cnt = 0;
	for (long long i = 2; i <= n; i *= 2) {
		cnt += n / i;
	}
	return cnt;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	long long a = div5(n) - div5(n - m) - div5(m);
	long long b = div2(n) - div2(n - m) - div2(m);
	cout << min(a, b);
}

 

https://github.com/proqk/Algorithm/tree/master/math

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