굳건하게

문제 : https://www.acmicpc.net/problem/3896

[알고리즘풀이]

에라토스테네스 체를 이용해서, Input 범위의 모든 값들에 대해서 소수인지 아닌지 판단할 수 있게 준비한다.

N이 들어오면, N이 소수가 아니라면 왼쪽으로 소수가 나올 때까지 순회하고, 오른쪽으로 소수가 나올때까지 순회해

가장 가까이에 있는 왼쪽 소수와 오른쪽 소수를 찾아 그 사이의 Gap을 출력한다.

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

bool p[1300000];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	for (int i = 2; i < 1300000; i++) {
		if (p[i] == false) {
			for (int j = 2 * i; j < 1300000; j+= i)
				p[j] = true;
		}
	}
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int n;
		cin >> n;
		int L = n, R = n;
		while (p[L] == true)
			L--;
		while (p[R] == true)
			R++;
		cout << R - L << '\n';
	}
}

문제 : https://www.acmicpc.net/problem/3474

[알고리즘풀이]

정수 K에서 뒤에 붙는 0의 개수는 K를 소인수 분해했을 때, 소수 2와 5로 만들 수 있는 10의 최대 개수랑 같다.

즉, K를 소인수분해했을 때, 2와 5의 개수 중 작은 값이랑 같다.

=> N! 을 소인수 분해했을 때, 2와 5의 개수 중 작은 값을 출력하면 된다.

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int n, count_2 = 0, count_5 = 0;
		cin >> n;
		for (int j = 1; ; j++) {
			if ((long long)pow(2, j) <= n)
				count_2 += n / (long long)pow(2, j);
			else
				break;
		}
		for (int j = 1; ; j++) {
			if ((long long)pow(5, j) <= n)
				count_5 += n / (long long)pow(5, j);
			else
				break;
		}
		cout << min(count_2, count_5) << '\n';
	}
}

문제 : https://www.acmicpc.net/problem/2153

[알고리즘풀이]

주어진 Input을 규칙에 맞춰 정수로 바꾸고, 그 정수가 소수인지 판단한다.

( 소수인지, 아닌지는 에라토스테네스체를 이용. )

#include<iostream>
#include<string>

using namespace std;

bool p[1050];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	for (int i = 2; i < 1050; i++) {
		if (p[i] == false) {
			for (int j = 2 * i; j < 1050; j += i)
				p[j] = true;
		}
	}
	string input;
	cin >> input;

	int n = 0;
	for (int i = 0; i < input.length(); i++) {
		if ('a' <= input[i] && input[i] <= 'z') {
			n += input[i] - 'a' + 1;
		}
		else {
			n += input[i] - 'A' + 27;
		}
	}
	if (p[n] == false)
		cout << "It is a prime word.";
	else
		cout << "It is not a prime word.";
	return 0;
}

문제 : https://www.acmicpc.net/problem/16288

[알고리즘풀이]

A[] : 입국장을 빠져나가는 순서를 담은 배열.

k : 여권 심사 창구의 수.

C : A배열에서 순증가부분수열의 수.

라고 한다면 k 가 C보다 크거나 같으면 항상 원하는 순서대로 입국장을 빠져나갈 수 있다.

ex)

A[] : 4 1 3 2 5 6 8 9 7 10 라고 하자.

A배열의 순증가부분수열은 4 - 5 - 6 - 8 - 9 - 10 / 1 - 3 - 7 / 2 로 총 3개이다.

즉, 창구가 3개 이상이면 각 창구마다 위의 수열대로 배치를 할 수 있다.

#include<iostream>

using namespace std;

bool check[101];
int A[100];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> A[i];
	int c = 0;
	for (int i = 0; i < n; i++) {
		if (check[A[i]] == false) {
			c++;
			int last = A[i];
			for (int j = i; j < n; j++) {
				if (last <= A[j] && check[A[j]] == false) {
					last = A[j];
					check[A[j]] = true;
				}
			}
		}
	}
	if (c <= k)
		cout << "YES\n";
	else
		cout << "NO\n";
	return 0;
}