문제 설명: N개의 정수가 주어질 때, 각 숫자의 뒤에 0~9 사이의 숫자를 붙이는 방법으로만 정렬을 수행할 수 있다. 오름차순으로 정렬되도록 숫자를 붙일 때 최소 횟수를 반환하라.
접근법: 정렬을 만족하려면 A[i-1] < A[i] 이어야 하고, 최소한으로 숫자를 붙이려면 A[i-1] >= A[i] 일 때 A[i]에 숫자를 붙이고 난 수가 가능한 작은 수여야 함. 숫자를 붙이는 방법은 A[i-1] >= A[i] 일 때 3가지 경우로 나뉨
맨 처음에 A[i]의 자릿수만큼 A[i-1]의 앞에서부터 비교 --> A[i-1]의 prefix 라고 하자.
숫자가 같은 경우 "남은 A[i-1]의 숫자에서 +1" 한 숫자들을 A[i]의 뒤에 붙여준다.
e.g. A[i-1] = 3289, A[i] = 32 --> 3290
주의할 점: +1할 때 자리 올림이 발생해서 prefix 에서 숫자가 바뀌어야 되는 경우 예외 처리를 해주어야 함. 남은 A[i-1]의 숫자 개수 + 1 만큼 0을 A[i]의 뒤에 붙여준다.
e.g. A[i-1] = 1999, A[i] = 19 --> 19000
A[i]가 더 큰 경우, 남은 A[i-1]의 숫자 개수만큼 0을 A[i]의 뒤에 붙여준다.
e.g. A[i-1] = 3223, A[i] = 41 --> 4100
A[i-1]이 더 큰 경우, 남은 A[i-1]의 숫자 개수 + 1 만큼 0을 A[i]의 뒤에 붙여준다.
e.g. A[i-1] = 312, A[i] = 23 --> 23000
주의할 점: N <= 100 이고 숫자가 10^9 까지 있으므로 최대 10^109 인 숫자가 잇을 수 있기 때문에 문자열로 처리해야 함
맨 처음에 숫자를 비교할 때 문자열의 경우 앞 글자부터 큰 값이면 큰 것으로 간주하기 때문에 먼저 길이를 비교해주어야 함
A[i]의 길이가 길다면 skip
A[i-1]과 A[i]의 길이가 같은데 A[i]가 사전순으로 뒤에 오면 skip
A[i-1]과 A[i]의 길이가 같은데 A[i]가 사전순으로 앞에 오면 A[i]의 뒤에 0을 붙임
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const static int _ = []() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
return 0;
}();
void solve() {
int N;
cin >> N;
string A[N];
for (int i = 0; i < N; i++) cin >> A[i];
int ans = 0;
for (int i = 1; i < N; i++) {
int prev_len = A[i-1].size();
int curr_len = A[i].size();
if ((prev_len < curr_len) or (prev_len == curr_len and A[i-1] < A[i])) continue;
// A[i-1] >= A[i]
string prefix = A[i-1].substr(0, curr_len);
if (prefix > A[i]) {
int num_zeors = prev_len - curr_len + 1;
A[i] += string(num_zeors, '0');
ans += num_zeors;
} else if (prefix < A[i]) {
int num_zeors = prev_len - curr_len;
A[i] += string(num_zeors, '0');
ans += num_zeors;
} else {
int sz = prev_len - curr_len + 1;
vector<int> v(sz, 0);
v[0] = 1;
// 계산 편의를 위해 맨 뒤의 숫자부터 계산
for (int j = prev_len-1; j >= prefix.size(); j--) {
int v_pos = prev_len - 1 - j;
int x = A[i-1][j] - '0';
if (x + v[v_pos] > 9) v[v_pos+1] = 1; // carry
v[v_pos] = (x + v[v_pos]) % 10;
}
if (v.back() == 1) { // prefix 부분에서 carry가 발생한 경우
A[i] += string(sz, '0');
ans += sz;
} else {
v.pop_back(); // except carry
while (!v.empty()) {
A[i].push_back(v.back() + '0');
v.pop_back();
}
ans += sz - 1;
}
}
}
cout << ans << endl;
}
int main() {
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
Prime Time
문제 설명: 카드를 두 그룹으로 나누는데, 한 그룹의 카드에 적힌 숫자의 합은 다른 그룹의 카드에 적힌 숫자의 곱과 같아야 한다. 카드에 적힌 숫자는 모두 소수이며, 같은 숫자를 가진 카드가 존재할 수 있다. 각 카드는 반드시 하나의 그룹에만 속해야 하며, 각 그룹은 적어도 하나의 카드를 포함해야 한다. 카드가 하나인 경우 그룹의 합이나 곱은 그 카드에 적힌 숫자이다. 두 그룹 중 카드에 적힌 숫자들의 합을 점수로 할 때 최대 점수를 구하라.
입력으로 M 이 주어지고, 그 다음 M 줄에는 각각 Pi, Ni 가 주어진다. Pi는 카드에 적힌 숫자이며, Ni는 Pi가 적힌 카드의 개수이다.
Test Set 1: 카드의 총 개수는 2 ~ 10 사이이다.
Test Set 2: 카드의 총 개수는 2 ~ 100 사이이다.
Test Set 3: 카드의 총 개수는 2 ~10^15 사이이다.
Pi는 2~499 사이의 소수이다.
첫번째 접근법: naive하게 각 카드를 하나씩 나누어서 두 그룹의 합과 곱을 계속 비교해서 최댓값을 탐색한다. Test Set 1에서 카드의 총 개수는 최대 10으로 두 그룹으로 나누는 경우의 수는 10C1 + 10C2 + ... + 10C9 = 914 이고 나눌 때마다 합과 곱을 비교해야 하므로 10회 반복문이 필요하게 된다. 시간 복잡도는 최대 9140 으로 충분히 해결할 수 있다.
#include <iostream>
#include <vector>
#include <algorithm>
#define sz(c) (int)(c).size()
using namespace std;
typedef long long ll;
const static int _ = []() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
return 0;
}();
ll best;
void dfs(int pos, int checked, ll sum, vector<int>& deck) {
ll product = 1;
for (int i = 0; i < sz(deck); i++) {
if (checked & (1 << i)) continue;
product *= deck[i];
}
if (product == 1) return;
if (sum == product) best = max(sum, best);
for (int i = pos; i < sz(deck); i++)
dfs(i+1, checked | (1 << i), sum + deck[i], deck);
}
void solve() {
int M;
cin >> M;
vector<int> v;
for (int i = 0; i < M; i++) {
int p, n;
cin >> p >> n;
while (n--) v.push_back(p);
}
best = 0;
dfs(0, 0, 0, v);
cout << best << endl;
}
int main() {
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
두번째 접근법: Test Set 2 는 N <= 100 이기 때문에 위의 풀이대로 할 경우 시간 초과로 해결할 수 없다. 또한 2가 100번 곱해진다면 곱의 최댓값이 long long의 범위를 벗어날 수 있다. 그러나 합은 카드의 최대 소수인 499가 100번 더해지면 49900 (합의 최댓값) 이기 때문에 어차피 49900 보다 큰 곱은 볼 필요가 없음을 알 수 있다. 위의 풀이에서 주어진 카드의 모든 숫자를 더한 합보다 지금 곱이 크거나 같을 경우 가지치기를 함으로써 시간 복잡도를 줄일 수 있다.
이전과 다르게 최대 합에서 하나씩 원소를 빼서 다른 그룹으로 옮기는 경우를 탐색한다. (계산의 편의를 위함)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const static int _ = []() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
return 0;
}();
ll dfs(int pos, ll sum, ll product, vector<int>& deck) {
if (sum < product) return 0;
if (sum == product) return sum;
ll ret = 0;
for (int i = pos; i < deck.size(); i++)
ret = max(ret, dfs(i+1, sum - deck[i], product * deck[i], deck));
return ret;
}
void solve() {
int M;
cin >> M;
vector<int> deck;
ll upper_bound = 0;
for (int i = 0, p, n; i < M; i++) {
cin >> p >> n;
upper_bound += p*n;
while (n--) deck.push_back(p);
}
cout << dfs(0, upper_bound, 1, deck) << endl;
}
int main() {
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
세번째 접근법: Test Set 3 에서 N은 최대 10^15 이기 때문에 위의 방법은 메모리 초과 및 시간 초과로 문제를 해결할 수 없다. 약간 수학적인 추리가 필요한데, 첫번째 그룹의 카드 합과 두번째 그룹의 카드 곱이 같다는 점과 카드에 적힌 숫자의 범위 2~499 사이의 소수라는 점에서 다음과 같은 정보를 알 수 있다.
N = 10^15 일 때, 첫번째 그룹이 최대로 가질 수 있는 숫자 합은 499 * 10^15 이며, 이는 2^60 보다 작은 수이다.
따라서 두번째 그룹의 카드를 곱해서 만들어질 수 있는 숫자도 2^60 보다 작다. 물론 모든 카드가 2일 때는 모든 카드가 499일 수 없기 때문에 그룹 곱의 상한으로 생각하면 될 것이다. 아무튼 2^60 보다 작다는 의미는 모든 숫자가 2일 때 카드가 60장 쓰일 때보다 적은 개수의 카드가 사용될 수 밖에 없다. 즉, 두번째 그룹의 카드는 최대 60장이다.
두번째 그룹의 카드에 적힌 숫자의 합은 최대 499 * 60 = 29940 이다. 여기서 60은 소수 2만 가정한 것이므로 실제로는 훨씬 적은 값일 것이다.
첫번째 그룹의 카드에 적힌 숫자 합은 모든 카드의 숫자 합에서 두번째 그룹의 카드에 적힌 숫자 합을 뺀 것과 같다. 따라서 첫번째 그룹의 카드에 적힌 숫자 합은 최소 "모든 카드의 숫자 합 - 29940"이 된다. 물론 주어진 카드로 29940을 만들 수 없으면 최대 만들 수 있는 값이 될 것.
정리하자면, 2~29940 사이의 숫자를 X라고 할 때 "모든 카드의 숫자 합 - X"가 주어진 카드로 나누어 떨어지는 경우(=두번째 그룹의 카드들을 곱해서 만들 수 있는 경우)가 있다면 가장 작은 X에 대해 "모든 카드의 숫자 합 - X"가 첫번째 그룹의 카드로부터 나온 최대합이 된다.
모든 카드에 적힌 숫자의 합이 29940 보다 작으면 그 합을 X의 상한으로 두면 된다.
29940번 반복문을 돌리면서 모든 카드마다 나누어 떨어지는지 시도하면 되는데, 카드의 종류는 최대 95가지이므로 충분히 시간 안에 해결 할 수 있다. 2~499 사이의 소수는 95개이다.
"모든 카드의 숫자 합 - X" 에서 나누어 떨어지는 카드를 모두 합한 값이 X가 된다면, 나누어 떨어지지 않은 카드의 합은 반드시 "모든 카드의 숫자 합 - X"가 되기 때문에 두번째 그룹에 포함될 카드만 찾아내도 문제를 해결할 수 있다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const static int _ = []() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
return 0;
}();
void solve() {
int M;
cin >> M;
ll deck[M][2];
ll ans = 0, upper_bound = 29940, sum = 0;
for (int i = 0; i < M; i++) {
cin >> deck[i][0] >> deck[i][1];
sum += deck[i][0] * deck[i][1];
}
if (sum < upper_bound)
upper_bound = sum;
for (ll x = 2; x < upper_bound; x++) {
ll product = sum - x;
ll card_sum = 0; // the sum of cards in product group
bool matched = true;
for (int i = 0; i < M and matched; i++) {
int num_used_cards = 0;
while (product % deck[i][0] == 0) {
product /= deck[i][0];
card_sum += deck[i][0];
num_used_cards++;
}
if (num_used_cards > deck[i][1])
matched = false;
}
if (matched and product == 1 and card_sum == x) {
ans = sum - x;
break;
}
}
cout << ans << endl;
}
int main() {
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
Hacked Exam
문제 설명: N명의 학생이 Q개의 질문에 대답한 결과와 점수가 주어질 때, 학생들의 답변을 참고하여 점수의 기댓값이 최대가 되도록 답변을 구성하여 출력. 점수는 z/w 형태로 기약분수로 표현해야 함.
Test Set 1: 1 <= N <= 2, 1 <= Q <= 10
Test Set 2: 1 <= N <= 2, 1 <= Q <= 40
Test Set 3: 1 <= N <= 3, 1 <= Q <= 120
질문의 답변은 T와 F로 2가지 이며, 각 학생들의 시험 결과는 T와 F로 구성된 Q 글자의 문장이다.
점수는 각 문제당 1점이며, 각 학생의 점수 Si 는 0~Q 사이의 숫자이다.
접근법: (참.. 문제 이해하는 것도 오래 걸리고, 해석을 보고 이해하는 것도 오래 걸린 문제)
기댓값의 정의를 살펴보면, 각 사건이 발생했을 때 얻는 이득과 그 사건이 발생할 확률을 곱한 것의 합이라고 한다. 여기서 사건은 어떤 질문 q에 대한 답변이 참(true)인 경우를 의미하며, 그 사건이 발생할 확률이란 어떤 질문 q에 대한 답변이 참(true)일 확률을 뜻한다. 사건이 발생했을 얻는 이득은 1점이기 때문에 기댓값을 구할 때 확률의 합만 계산하면 된다.
질문 q에 대한 답변이 참일 확률을 Pq라고 할 때, 최대 기댓값 := max(P1 + P2 + ... + Pq)
단, 답변이 T와 F로 2가지이기 때문에 각 질문에 대한 확률은 답변이 T일 때 참일 확률과 답변이 F일 때 참일 확률 중 큰 값으로 해야 기댓값이 최대가 된다. 즉, Pi = max(Pi(ans = T), Pi(ans = F)) 이고 E(Q) = P1 + P2 + ... + Pq
그러면 답변이 참일 확률은 어떻게 구할 수 있는가? 학생의 점수를 이용
어떤 학생의 점수가 S일 때, 각 질문에 대한 그 학생의 답변은 S / Q 의 확률을 가진다. 질문 q에 대한 답이 T일 때 참일 확률을 Pt 라고 하고 답이 F일 때 확률을 Pf 라고 하자. 만약 이 학생이 어떤 질문에 T 라고 답했다면 Pt = S / Q 가 되고, 반대로 Pf = 1 - Pt = 1 - S / Q 가 된다.
e.g. 1명의 학생의 답변이 FFT 이고 점수가 2점일 때, 3개의 질문 중 2개가 정답이니 학생이 답변한 F, F, T 각각이 참이 될 확률은 2/3이다.
1번 질문에 답변 F가 참일 확률: Pf = 2/3 <=> 반대로 답변 T가 참일 확률: Pt = 1/3
2번 질문에 답변 F가 참일 확률: Pf = 2/3 <=> 반대로 답변 T가 참일 확률: Pt = 1/3
3번 질문에 답변 F가 참일 확률: Pf = 1/3 <=> 반대로 답변 T가 참일 확률: Pt = 2/3
매 질문마다 최대가 되는 확률값을 골라서 더할 경우, E(Q) = Pf + Pf + Pt = 2/3 + 2/3 + 2/3 = 6/3 = 2/1 = 2 가 된다.
이 예시에서 기댓값이 최대가 되는 답변 케이스가 FFT 인 것은 자명하다.
그러나 반드시 확률을 구할 필요가 없다. 단순히 생각해보면 1명의 학생이 절반이상 맞췄다면 그 학생의 답변을 그대로 제출하는게 할 수 있는 최대의 점수를 내는 것이다. 반대로 절반도 못 맞췄다면 그 학생의 답변과는 정반대로 답하면 "Q - 학생의 점수"를 얻을 수 있을 것이고 이 점수가 최대의 예상 점수가 된다.
어차피 확률을 계산해도 점수가 낮다면 학생의 반대 답변을 정답으로 하게 된다.
만약 2명 학생의 답변을 가지고 있다면?
여기서부터는 크게 2가지로 나뉘어서 생각해야 한다. 두 학생의 답변이 같은 경우와 두 학생의 답변이 다른 경우이다.
두 학생의 답변이 같은 경우 N = 1 일 때와 비슷하게 동작하면 되는데, 두 학생의 점수를 합한 것이 절반보다 크다면 같은 답변이 많을 수 밖에 없고 이 답변을 그대로 제출해야 예상 점수를 최대화할 수 있을 것이다. 반대로 두 학생의 점수를 합한 것이 절반도 못된다면 당연히 반대로 답변을 제출해야 한다. (둘이 합쳐서 절반도 못맞췄다면 반대 답변을 내야 한다.)
두 학생의 답변이 다른 경우는 오히려 더 쉽다. 점수가 높은 학생의 답변을 그대로 제출하면 된다.
두 학생이 같은 대답을 한 질문의 집합을 A라고 할 때, A 중 x개의 질문의 답변이 참이라면 (여기서 두 학생 모두 x점을 획득) A에 속한 질문에 올바르게 답할 확률 Pq = x / |A| 이다. 반대로 올바르지 않게 답할 확률은 1 - Pq 이다. 여기서 우리는 두 확률 중 더 큰 것을 골라야 한다. 따라서 올바른 답변의 기댓값은 매 질문마다 큰 값을 더한 결과이다.
그리고 더 큰 값이 결국에는 두 학생의 점수를 합했을 때 Q보다 크면 학생들의 답변과 같은 것이 되고, Q보다 작으면 학생들의 답변의 반대가 된다.
각 질문의 점수가 1점이기 때문에 실제로 확률을 합한 것은 얻은 점수이므로 확률을 계산해줄 필요는 없다.
sum(max(Pq, 1-Pq)) for q in A --> max(x, |A| - x)
A 에 속하지 않은 질문들에 대해 (두 학생이 답변을 다르게 한 질문들) 두 학생은 반드시 Si - x 점수를 가져야 한다. 그리고 각 학생이 남은 질문에 대해 올바르게 답할 확률은 Pi,q = (Si - x) / (Q - |A|) 이다. 반대로 올바르게 답하지 않을 확률은 1 - Pi,q 이다.
따라서 나머지 질문에 대해 올바른 답변을 할 기댓값은 sum(max(P1q, 1 - P1q, P2q, 1 - P2q)) for q not in A 이고 위와 마찬가지로 확률을 실제로 계산해줄 필요 없이 점수로 나타낼 수 있다. --> max(S1 - x, S2 - x, Q - |A| - (S1 - x), Q - |A| - (S2 - x))
이를 그림으로 표현해보자. 편의상 동일한 답변을 한 질문들이 왼쪽에 있고, 다르게 답변한 질문이 오른쪽에 있다고 가정한다.
먼저 왼쪽 그림에서 두 학생이 같은 답변을 한 경우 실제로 비교해야할 확률은 2가지이다. X개의 질문들을 맞췄을 때 참일 확률과 A-X개의 질문들을 맞췄을 때 참일 확률이 비교 대상이다. 언급했다시피 실제 확률의 합은 결국 점수 합과 같으므로 X와 A-X 를 비교하면 된다.
다음 오른쪽 그림에서 두 학생이 다른 답변을 한 경우 비교해야할 확률은 4가지이다. X개의 질문을 이미 맞추었다고 가정하면 다르게 답변한 질문들에서 두 학생이 얻은 점수는 S1-X 와 S2-X가 될 것이고 이 점수를 얻은 질문들은 서로 겹치지 않는다. 즉, 상호 배타적이다. 그리고 점수를 얻지 못한 질문에 대해 참일 확률은 1 - P(S1-X) 로 쉽게 계산할 수 있고 아래 그림에서 나타낸 4개의 박스에 대해 확률 중 큰 값을 선택하면 된다. 마찬가지로 확률의 합은 점수 합과 같으므로 정리해보면 Q-A 영역에 속한 질문에 대한 점수의 최대 기댓값은 max(max(S1-X, Q-A-(S1-X)), max(S2-X, Q-A-(S2-X))) 가 된다.
그렇다면, X는 어떨 때 가장 크고 작은지 알아낼 필요가 있다. 물론 재귀 함수로 하나씩 다 시도해볼 수 있겠지만 다음의 수식에서 쉽게 상한과 하한을 찾을 수 있다.
