코드 복사/붙여넣기 하는 당신이 아름답습니다.

원래 나도 대회 참가하려고 했었는데 귀찮아서 대회 접수를 까먹어버렸다 ㅋㅋ;;

빨리 접수하라고 전화까지 왔었는데 흑

대충 문제만 듣고 풀어보았다.

문제 풀이 순서는 내 맘대로 ㅎㅎ

1. Maidas Number

풀이

1에서 n까지의 자연수들 중에서 소인수의 최대값이 m보다 작은 수의 갯수를 세는 문제이다.

일단 소인수는 모두 소수이므로 소수를 구해둔 뒤 모든 1~n 자연수를 검사해주면 된다.

어떤 자연수 k에 대해 m 이상의 소수를 약수로 가진다면 이는 조건에 불일치하는 것이므로 컷 해주면 된다.

제한시간이 10초인 걸로 아는데 음…

내가 정해를 모르는 건지는 모르겠지만 딱히 빠른 솔루션이 없다면 그닥 좋은 문제는 아닌 것 같다.

코드

#include <stdio.h>

const int n_ = 1e5 + 1;
int n, m, cnt;
bool chk[n_];

int main() {
	scanf("%d %d", &n, &m);

	chk[1] = 1;
	for (int i = 2; i*i <= n; i++) {
		if (chk[i]) continue;
		for (int j = i * 2; j <= n; j += i) chk[j] = 1;
	}

	for (int i = 2; i <= n; i++) {
		int mx = 0;
		for (int j = m + 1; j <= i; j++) {
			if (!chk[j] && !(i%j)) {
				mx = j;
				break;
			}
		}
		if (mx <= m) cnt++;
	}
	
	printf("%d", cnt);

	return 0;
}

2. Prime Sum

풀이

m ~ n 사이 자연수들 중 소수의 합을 구하는 문제다.

이 문제 풀이가 궁금해서 들어온 사람은 없을 것 같으니 풀이는 생략한다.

코드

#include <stdio.h>

typedef long long ll;
const int n_ = 2e5 + 1;
int n, m;
ll sum;
bool chk[n_];

int main() {
	scanf("%d %d", &m, &n);

	chk[1] = 1;
	for (int i = 2; i*i <= n; i++) {
		if (chk[i]) continue;
		for (int j = i * 2; j <= n; j += i) chk[j] = 1;
	}

	for (int i = m; i <= n; i++) if (!chk[i])
		sum += (ll)i;

	if (!sum) puts("-1");
	else printf("%lld", sum);

	return 0;
}

3. Get Password

풀이

m개의 숫자가 주어질 때, 길이 n짜리 비밀번호의 갯수(순열의 갯수)를 구해야 한다.

단, 비밀번호에 적어도 1개 이상의 짝수와 홀수가 포함되어야 하며 숫자는 오름차순으로 배열한다. (중복 숫자는 없음)

n 제한이 크지 않으므로 모든 경우를 다 돌아보면 된다.

홀수의 개수가 0이나 n인 경우는 홀/짝에 편중된 경우이므로 컷 해준다.

코드

#include <stdio.h>
#include <algorithm>
using namespace std;

const int n_ = 10 + 1;
int n, m, ans, odd, num[n_], abc[n_];

void dfs(int now) {
	if (now == n + 1) {
		if (odd > 0 && odd < n) ans++;
		return;
	}
	for (int i = 1; i <= m; i++) {
		if (abc[now - 1] < num[i]) {
			abc[now] = num[i];
			odd += num[i] % 2;
			dfs(now + 1);
			odd -= num[i] % 2;
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) scanf("%d", &num[i]);
	sort(num + 1, num + m + 1);
	abc[0] = -987654321;
	dfs(1);
	printf("%d", ans);
	return 0;
}

4. Trump Card

풀이

모양이 같고 숫자만 다른 트럼프 카드 13개 2쌍이 주어진다.

가장 긴 공통 부분 수열? 이름이 이게 맞나? 아무튼 그거의 길이를 구하는 문제다.

전형적인(전형적이지 않은가? 아무튼) LIS 문제이다.

이거를 풀 수 있다면 이 문제도 풀 수 있다.

dp로 O(n^2)에 짜거나 이분 탐색으로 짜도 되는데

lower_bound를 사용하면 코드도 간결하고 빠르고 편하다.

코드

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

int len, ans[14];
string a[14], b[14];

int main() {
	for (int i = 0; i < 13; i++) cin >> a[i];
	for (int i = 0; i < 13; i++) cin >> b[i];

	for (int i = 0; i < 13; i++) {
		int p;
		for (int j = 0; j < 13; j++) {
			if (a[i] == b[j]) {
				p = j;
				break;
			}
		}
		auto it = lower_bound(ans, ans + len, p);
		if (*it == 0) len++;
		*it = p;
	}
	cout << len;

	return 0;
}

5. Line Draw

풀이

n이 주어진다.

1부터 2*n의 숫자를 원순열로 오름차순으로 배열하고 겹치지 않는 n개의 숫자쌍을 골라 선을 이을 때

선이 하나라도 겹치는 경우의 수를 세는 문제이다.

이거 완전탐색해서 스택으로 이렇게 짰었는데…

bool iscross() {
	bool chk[22] = { 0 };
	for (int i = 1; i <= n * 2; i++) {
		if (!chk[i]) {
			chk[i] = chk[con[i]] = 1;
			stk.push(i);
		}
		else {
			if (stk.top() == con[i]) stk.pop();
			else return true;
		}
	}
	return false;
}

void dfs(int now) {
	if (now == n * 2 + 1) {
		if (iscross()) ans++;
		return;
	}
	if (con[now]) {
		dfs(now + 1);
	}
	else {
		for (int i = 1; i <= n * 2; i++) {
			if (i != now && !con[i]) {
				con[i] = now, con[now] = i;
				dfs(now + 1);
				con[i] = con[now] = 0;
			}
		}
	}
}

짜고보니 시간복잡도를 무시했음을 깨달았다.

‘아 이거 확통으로 풀리겠다’ 하고 코드를 지웠다.

확통을 몰라도 풀 수야 있겠지만 문제를 푸는데 조금 어려움이 있을 거라 생각한다.

겹치는 경우의 수를 구하는 건 너무 복잡한 것 같아서 불가능 한 것 같아서

전체 경우의 수에서 겹치지 않는 경우의 수를 빼줬다.

선을 잇는 경우의 수는 n개의 숫자에서 2개를 뽑고, 또 n-2개의 숫자에서 2개를 뽑는 걸 반복하는 경우의 수와 같으므로

전체 경우의 수 = nC2 * (n-2)C2 * (n-4)C2 * ... * 2C2 / n!

이고 문제는 겹치지 않는 경우의 수 인데

일단 겹치지 않으려면 원을 반으로 가르는 임의의 두 숫자를 이었을 때 생기는 양쪽 반원이 있을 것이다.

각 반원에 포함된 숫자의 갯수가 짝수여야만 겹치지 않게 선을 이을 수 있다.

모르겠다면 직접 그려보면 직관적으로 알 수 있다. (그림 그려서 올리기 귀찮음)

각 반원에 대해서 겹치지 않는 경우의 수는 어떻게 구할까?

반원에서 겹치지 않는 경우의 수도 원에서 겹치지 않는 경우의 수와 같으므로

이전에 미리 구해둔 경우의 수를 재활용하면 된다.

양쪽 반원에서 나올 수 있는 경우의 수를 곱해주면 dp[k]를 구할 수 있다.

양쪽 반원에 포함되는 숫자의 갯수는 k-2를 2개의 짝수로 분할하는 경우의 수와 같다.

k개의 숫자에서 임의의 두 숫자를 기준으로 반원을 나눴으니 k-2개의 숫자를 분할하면 된다.

이제 식을 정리하면 다음과 같다.

겹치지 않는 경우의 수 = n-2를 2개의 짝수로 분할하는 경우의 수

겹치는 경우의 수 = 모든 경우의 수 - 겹치지 않는 경우의 수

값이 int를 넘어가니 long long을 사용하자.

코드

#include <stdio.h>
typedef long long ll;

ll dp[22];

int main() {
	int n;
	scanf("%d", &n);

	ll sum = 1;
	for (int i = 2; i <= n * 2; i += 2) sum *= ((ll)i * (i - 1) / 2);
	for (int i = n; i; i--) sum /= i;

	dp[0] = dp[2] = 1;
	for (int k = 4; k <= 20; k += 2) {
		for (int i = 0; i <= k - 2; i += 2) {
			int j = k - 2 - i;
			dp[k] += dp[i] * dp[j];
		}
	}

	printf("%lld", sum - dp[n * 2]);

	return 0;
}

6. Sale Event

풀이

길이 n의 수열이 주어지고, 연속된 원소 정확히 3개를 부분 집합으로 묶을 수 있다.

이때 부분 집합의 갯수는 상관없고 각 부분 집합끼리 겹쳐서는 안 된다.

모든 부분 집합에 대해, 각 부분 집합에 포함된 숫자 중 가장 작은 숫자를 없앨 수 있을 때

원소를 적절히 묶어서 전체 수열의 합을 최소로 만들어야 한다.

이 문제와 유사하게 풀 수 있다.

일단 1~3, 2~4, 3~5, … (n-2)~n까지의 최솟값을 모두 구해서 배열 b에 넣는다. (변수 이름 죄송합니다 ㅋㅋ;;)

부분 집합이 서로 겹치지 못하므로, 각 부분 집합은 최소 3만큼 떨어져 있어야 한다.

n 이하인 임의의 숫자 k에 대해, dp[k]는 b[1]부터 b[k]까지의 최댓값으로 정의한다.

dp[k]는 dp[k-3]+b[k]이나, dp[k-1]이나, dp[k-2]가 될 수 있다.

이 셋 중 가장 큰 값을 dp[k]에 넣으면 된다.

따라서 점화식은 아래와 같다.

dp[k] = max(dp[k-3]+b[k], dp[k-2], dp[k-1])

코드

#include <stdio.h>
#include <algorithm>
using namespace std;

const int n_ = 2e3 + 1;
int n, a[n_], b[n_], dp[n_];

int main() {
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}

	for (int i = 2; i < n; i++) {
		int mn = 987654321;
		for (int j = i; j >= i - 2; j--) {
			mn = min(mn, a[j]);
		}
		b[i - 2] = mn;
	}

	dp[0] = b[0], dp[1] = b[1], dp[2] = b[2];
	for (int i = 2; i < n - 2; i++) {
		dp[i] = max(dp[i - 1], dp[i - 2]);
		dp[i] = max(dp[i], b[i] + dp[i - 3]);
	}

	int sum = 0;
	for (int i = 0; i < n; i++) sum += a[i];
	printf("%d", sum - dp[n - 3]);

	return 0;
}

아무말

마이다스 챌린지 대회 알고리즘 2017 풀이 기출문제 midas maidas challenge solution

wookje.kwon's profile image

wookje.kwon

2017-05-14 11:18

Read more posts by this author