빵개발연구소

트럼프카드 문제 (TrumpCard)

트럼프 카드가 얼마나 잘 섞였는지 판단하는 알고리즘을 개발하려고 합니다. 섞기 전의 카드 배열과 섞은 후의 카드 배열의 순서가 같은 부분배열들 중 섞기 전과 섞은 후에 공통으로 나타나며 길이가 가장 긴 것을 구해서 그 길이를 M 이라고 합니다. 그리고 M 값이 작을수록 카드가 잘 섞인 것으로 간주하기로 합니다. 이 때 부분배열은 연속되지 않아도 됩니다. 트럼프 카드는 모양이 없고 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A 로만 이루어진 것을 사용합니다.

예를 들어

[ 2, 3, 4 ] 와 순서가 같은 부분배열은 [ 2 ], [ 3 ], [ 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ], [ 2, 3, 4 ] 입니다. ( 연속되지 않아도 순서만 같으면 되기 때문에 [ 2, 4 ] 도 가능 )

카드 배열이 다음과 같다면

섞기 전 = [ 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A ]

섞은 후 = [ 3, J, 2, Q, 10, K, 4, 9, 5, 8, 6, A, 7 ]

두 카드 배열의 순서가 같은 부분배열 중 공통으로 나타나며 길이가 가장 긴 것은 [ 3, 4, 5, 6, 7 ], [ 3, J, Q, K, A ], … 등이 있으며 M 값은 5 가 됩니다.

주어진 카드 배열로 M 값을 구하는 프로그램을 작성하십시오.

입력

입력은 표준 입력(stdin)으로 주어지며

첫째 줄에 섞기 전 카드 배열이 주어집니다.

둘째 줄에 섞은 후 카드 배열이 주어집니다.

각 카드는 다음 문자열로 표현하며 카드와 카드는 공백으로 구분됩니다.

2 3 4 5 6 7 8 9 10 J Q K A

출력

출력은 표준 출력(stdout)으로 이루어집니다.

첫째 줄에 M 값을 출력합니다.

입력예)

2 3 4 5 6 7 8 9 10 J Q K A

3 J 2 Q 10 K 4 9 5 8 6 A 7

출력예)

5

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

int main()
{
	string Card1[13];
	string Card2[13];
	for (int i = 0; i < 13; i++)
	{
		string n;
		cin >> n;
		Card1[i] = n;
	}

	for (int i = 0; i < 13; i++)
	{
		string c;
		cin >> c;
		Card2[i] = c;
	}

	int Card_pos[13] = { 0 };
	int memo[13] = { 0 };
	for (int i = 0; i < 13; i++)
	{
		for (int j = 0;j < 13; j++)
		{
			if (Card1[i] == Card2[j])
			{
				Card_pos[j] = i;
				break;
			}
		}
	}

	for (int i = 12; i >= 0; i--)
	{
		for (int j = i; j < 13; j++)
		{
			if (Card_pos[i] <= Card_pos[j])
				memo[i] = max(memo[i], memo[j] + 1);
		}
	}

	cout << *max_element(memo, memo + 13);
	return 0;
}

소수합 문제 (PrimeSum)

철수는 학교에서 처음으로 소수에 대한 개념을 배웠고, 다음과 같은 숙제를 하나 받아왔습니다.

“100부터 200 사이에 있는 모든 소수들의 합을 구하시오.”

철수는 100부터 200까지 일일이 숫자 하나 하나가 소수인지를 따져 모든 소수를 구한 뒤 합을 구했습니다. 숙제를 해결하고 난 뒤 철수는 담임 선생님이 비슷한 유형의 숙제를 반복적으로 낸다는 것을 깨달았습니다. 개념이 유사한 숙제를 반복적으로 하는 것이 싫어진 철수는 여러분에게 이런 문제를 계산해주는 프로그램을 만들어 달라고 요청했습니다.

두 숫자를 입력 받아, 그 사이에 존재하는 모든 소수들의 합을 구하는 프로그램을 작성하십시오.

입력

입력은 표준 입력(stdin)으로 주어지며

첫째 줄에는 M이, 둘째 줄에는 N이 각각 주어집니다.( 1 <= N, M <= 200,000 )

단, N은 M보다 크거나 같습니다.( M <= N )

출력

출력은 표준 출력(stdout)으로 이루어집니다.

M <= 소수 <= N 을 만족하는 모든 소수들의 합을 구하시오. 단, 소수가 아예 없는 경우 -1을 출력합니다.

입력예)

100

200

출력예)

3167

입력예)

200

205

출력예)

-1

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

vector<int> GetPrimes(int num) 
{
	int *arr = new int[num + 1];
	for (int i = 2; i <= num; i++)
		arr[i] = i;

	vector<int> retPrimes;
	for (int i = 2; i <= num; i++)	
	{
		if (arr[i] == 0)
			continue;

		for (int j = i + i; j <= num; j += i) {
			arr[j] = 0;
		}
	}

	for (int i = 2; i <= num; i++)
	{
		if (arr[i] != 0)
			retPrimes.push_back(arr[i]);
	}
	delete arr;
	return retPrimes;
}

int main()
{
	int N, M;
	cin >> N;
	cin >> M;
	vector<int> v = GetPrimes(M);

	int sum = 0;
	for (int vn : v)
	{
		if (vn >= N && vn <= M)
			sum += vn;
	}

	if (sum == 0)
		sum = -1;

	cout << sum;
	return 0;
}

마이다스수 문제 (MidasNumber)

“마이다스수”는 어떤 자연수의 소인수중 최대값이 M보다 크지 않은 수를 의미합니다. 여기서 소인수란 주어진 자연수를 나누어 떨어뜨리는 약수 중에서 소수인 약수를 말합니다.

1보다 크고 N보다 작거나 같은 자연수 중에 “마이다스수”가 총 몇 개인지 구하는 프로그램을 작성하십시오.

예를 들어, N이 10이고 M이 3인 경우 소인수의 최대값이 3보다 작거나 같은 수들은 2, 3, 4, 6, 8, 9 로 “마이다스수”는 총 6개 입니다.

입력

입력은 표준 입력(stdin)으로 주어지며

첫째 줄에 N, 둘째 줄에 M이 주어진다. N은 100,000보다 작거나 같은 자연수이고, M은 100보다 작거나 같은 자연수입니다.

출력

출력은 표준 출력(stdout)으로 이루어집니다.

첫째 줄에 N보다 작거나 같은 “마이다스수”가 몇 개인지 출력합니다.

입력예)

10 3

출력예)

6

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

vector<int> GetPrimes(int num) //num까지의 소수 구하기
{
	int *arr = new int[num + 1];
	for (int i = 2; i <= num; i++)
		arr[i] = i;

	vector<int> retPrimes;
	for (int i = 2; i <= num; i++)	
	{
		if (arr[i] == 0)
			continue;

		for (int j = i + i; j <= num; j += i) {
			arr[j] = 0;
		}
	}

	for (int i = 2; i <= num; i++)
	{
		if (arr[i] != 0)
			retPrimes.push_back(arr[i]);
	}
	delete arr;
	return retPrimes;
}

int main()
{
	int N, M;
	cin >> N;
	cin >> M;	//M보다 작은 소수

	vector<int> primes = GetPrimes(M);

	int count = 0;
	for (int i = 2; i < N; i++)
	{
		for (int j : primes)
		{
			if (i%j == 0)
			{
				count++;
				break;
			}
		}
	}
	cout << count;
	return 0;
}