99코딩

문제

풀이

해당 문제의 규칙대로 반복할 시 아래 표와 같이 마지막에 열려 있는 창문들의 번호는 제곱수가 되므로 주어진 수 n이하의 제곱수의 개수를 구하면 된다.

#include <iostream>

using namespace std;

int main() {
	long long n;
	int cnt = 0;

	cin >> n;

	for (int i = 1; i * i <= n; i++)
		cnt++;

	cout << cnt;

	return 0;
}

문제

풀이

 주어질 수 있는 n의 최댓값이 1000000이므로 arr[1000001]을 선언하고 arr[i] = i가 되도록 채워준다.

이후 에라토스테네스의 체 방법을 이용해 소수가 아닌 수들을 걸러낸 후 더해서 n이 될 수 있는 두 소수들을 구한다. 두 소수가 같다면 cnt++을 한 번 더 해주고 cnt를 2로 나눈 몫을 리턴한다.

#include <iostream>

using namespace std;

int arr[1000001] = { 0, };

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);
    
    int t, n;

    for (int i = 2; i <= 1000000; i++)
        arr[i] = i;

    for (int i = 2; i * i <= 1000000; i++) {
        if (arr[i] == 0) continue;

        for (int j = i * i; j <= 1000000; j += i)
            arr[j] = 0;
    }

    cin >> t;

    for (int i = 0; i < t; i++) {
        int cnt = 0;

        cin >> n;

        for (int j = 2; j < n; j++) {
            if (arr[n - j] + arr[j] == n) {
                cnt++;

                if (n - j == j)
                    cnt++;
            }
        }

        cout << cnt / 2 << "\n";
    }

	return 0;
}

문제

풀이

에라토스테네스의 체를 이용해 주어진 범위 내의 소수의 개수를 구하였다.

#include <iostream>
#include <cmath>

using namespace std;

int main() {
	int a[246913];
	int n;
	
	cin >> n;

	while (1) {
		int count = 0;

	
		a[0] = 0;
		a[1] = 0;

		for (int i = 2; i <= 2 * n; i++)
			a[i] = 1;

		for (int i = 2; i <= int(sqrt(2 * n)); i++) {
			for (int j =2; i*j <= 2*n; j++) {
				a[i*j] = 0;                  
			}
		}

		for (int k = n+1; k <= 2 * n; k++) {
			if (a[k] == 1)
				count++;
		}


		cout << count << '\n';


		cin >> n;
		if (n == 0)
			break;
	}

}

문제

풀이

제곱근 판별법을 통해 소수를 찾아 출력하였다.

#include <iostream>

using namespace std;

bool isPrime(int n) {
	if (n == 0 || n == 1) return false;

	for (int i = 2; i * i <= n; i++)
		if (n % i == 0) return false;

	return true;
}

int main() {
	int n, m;

	cin >> n >> m;

	for (int i = n; i <= m; i++)
		if (isPrime(i)) cout << i << "\n";

	return 0;
}

문제

풀이

제곱근 판별법을 통해 주어진 수 n과 크거나 같은 소수 중 가장 작은 소수를 찾아 출력하였다.

#include <iostream>
#include <algorithm>

using namespace std;

bool isPrime(unsigned int n) {
	for (unsigned int i = 2; i * i <= n; i++)
		if (n % i == 0) return false;

	return true;
}

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

	int n;

	cin >> n;

	for (int i = 0; i < n; i++) {
		unsigned int num;

		cin >> num;

		if (num < 2) num = 2;
		else {
			while (true) {
				if (isPrime(num) == true) break;
				num++;
			}
		}

		cout << num << "\n";
	}

	return 0;
}

문제

풀이

먼저, 주어진 나무의 위치를 받아 오름차순으로 정렬한다. 그리고 각 나무 사이의 간격을 구하고 그 간격들의 최대공약수를 구한다. 이 최대공약수만큼의 간격을 가지고 나무를 심으면 가장 적게 심을 수있다.

(개수를 셀 때 -1을 해주는 것은 양 쪽에 나무가 심겨져 있기 때문이다.)

#include <iostream>
#include <algorithm>

using namespace std;

int trees[100000];
int betweenTree[100000];

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int main() {
	int n;
	int count = 0;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> trees[i];

	sort(trees, trees + n);

	for (int i = 1; i < n; i++)
		betweenTree[i - 1] = trees[i] - trees[i - 1];

	int interval = betweenTree[0];

	for (int i = 1; i < n - 1; i++)
		interval = gcd(interval, betweenTree[i]);

	for (int i = 0; i < n - 1; i++)
		count += betweenTree[i] / interval - 1;

	cout << count;

	return 0;
}

문제

풀이

기약분수의 분모는 두 분모의 최소공배수이고, 분자는 서로의 분자와 분모를 곱한 값 2개를 더한 값을 최대공약수로 나눈 값이다.

#include <iostream>

using namespace std;

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int main() {
	int a1, a2, b1, b2;

	cin >> a1 >> a2 >> b1 >> b2;

	int num1 = (a1 * b2) + (a2 * b1);
	int num2 = a2 * b2;

	cout << num1 / gcd(num1, num2) << " " << num2 / gcd(num1, num2);

	return 0;
}

문제

풀이

유클리드 호제법을 이용해 답을 구할 수 있다.

#include <iostream>
#include <algorithm>

using namespace std;

long long gcd(long long a, long long b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}

void swap(int& a, int& b) {
	int tmp = 0;

	tmp = a;
	a = b;
	b = tmp;
}

int main() {
	long long a, b;

	cin >> a >> b;

	swap(a, b);

	cout << a * b / gcd(a, b);

	return 0;
}