원래 나도 대회 참가하려고 했었는데 귀찮아서 대회 접수를 까먹어버렸다 ㅋㅋ;;
빨리 접수하라고 전화까지 왔었는데 흑
대충 문제만 듣고 풀어보았다.
문제 풀이 순서는 내 맘대로 ㅎㅎ
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