Closest Pick
- 문제 설명: N개의 티켓이 주어질 때 각 티켓은 1~K 사이의 정수를 가진다. 다른 티켓이 같은 정수를 가질 수도 있다. 1~K 사이의 정수 c가 랜덤으로 선택될 때 가지고 있는 티켓 중 하나가 N개의 티켓들보다 c에 가장 가까운 숫자일수록 이길 확률은 올라간다. 티켓 두 장을 구입해서 이길 확률을 최대화할 때 확률을 구하라.
- N개의 티켓에 적힌 숫자와 같은 티켓일 경우 어떤 점수도 얻지 못한다. 두 티켓이 모든 c에 대해 같은 차이를 가지기 때문이다.
- 입력
- 1 <= T <= 100
- 1 <= N <= 30
- Test Set 1: 1 <= K <= 30
- Test Set 2: 1 <= K <= 10^9
- 출력: 오차 10^-6 이하이면 ok
- 첫번째 접근법: Test Set 1은 K가 적기 때문에 브루트 포싱으로 해결할 수 있을 것이다.
- 먼저 N개의 티켓에 적힌 숫자들의 집합을 P라고 할 때, 1~K 사이의 모든 숫자에 대해 P에 있는 숫자들 중 가장 작은 차이(min_diff)를 구한다.
- P를 제외한 다른 숫자들 중에서 min_diff 보다 작은 차이를 가진 숫자를 찾는다. 참고로 숫자가 하나도 없다면 즉, P에 1~K 사이의 모든 숫자가 있다면 확률은 0이 될 것이다.
- 이전에 선택한 숫자 2개에 대해 확률을 계산해야 한다. 확률은 P에 있는 숫자들보다 가까운 c의 개수를 K로 나눈 것이 된다. 이 확률의 의미는 모든 가능한 c에서 몇 개의 c가 가장 가까운지에 대한 것이다.
- 여기서 P에 속한 숫자들을 제외한 것들 중 2개를 고르는 경우의 수는 (K-|P|)C(2) 이다. 여기서 C는 이항계수이다. Test Set 1은 K가 적기 때문에 브루트 포싱으로 해결할 수 있다.
- 시간 복잡도: O(K^3)
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
void solve() {
int N, K;
cin >> N >> K;
set<int> tickets;
for (int i = 0, tmp; i < N; i++) {
cin >> tmp;
tickets.insert(tmp);
}
int min_diff[K];
for (int c = 1; c <= K; c++) {
int& diff = min_diff[c-1];
diff = 1e9;
for (auto& t : tickets)
diff = min(diff, abs(t-c));
}
int max_wins = 0;
for (int a = 1; a <= K; a++) {
if (tickets.find(a) != tickets.end()) continue;
for (int b = a; b <= K; b++) {
if (tickets.find(b) != tickets.end()) continue;
int wins = 0;
for (int c = 1; c <= K; c++)
if (abs(a-c) < min_diff[c-1] or abs(b-c) < min_diff[c-1])
wins++;
max_wins = max(max_wins, wins);
}
}
double ans = (double)max_wins / K;
ans = round(ans * 1e6) / 1e6;
cout << ans << endl;
}
int main() {
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cout << "Case #" << tc << ": ";
solve();
}
return 0;
}- 두번째 접근법: Test Set 2 부터는 K가 너무 크기 때문에 모든 c에 대해 시도해볼 수 없다. 두 숫자를 선택할 때 후보의 개수를 줄일 필요가 있다. P에 속한 숫자의 좌우 양 옆의 숫자들이 후보에 적합한데 그 이유는 P에 속한 숫자로부터 멀리 떨어진 숫자를 선택하게 되면 P에 속한 숫자와 선택한 숫자 사이의 중앙값을 기준으로 가까운 숫자들이 나뉘게 되기 때문이다. 예를 들어 P=[1,2,3,7] 이고 K=7일 때 3 4 5 6 7 에서 5를 선택하는 것보다 4 또는 6을 선택하는 것이 가까운 숫자들을 더 많이 포함하게 된다. (5를 선택하면 숫자 5 1개만 가까운 숫자이지만, 4와 6을 선택하게 되면 4,5 또는 5,6을 가까운 숫자로 얻게 된다.)
- 또한, 후보에 있는 숫자들은 가까운 c의 개수를 계산할 때 어차피 P에 속한 숫자 사이에만 위치하기 때문에 1~K 사이의 모든 숫자에 대해서 가까운 c의 개수를 계산할 필요가 없다. 단순히 후보 숫자의 양 옆에 있는 Pi-1과 Pi 와의 차이를 계산하면 될 것이다. 그 외의 숫자는 어차피 Pi-1과 Pi와 더 가깝기 때문이다.
- 처음에 후보 숫자들을 고를 때 가까운 c의 개수를 미리 계산할 수 있고, 이후에 가까운 c의 개수를 내림차순으로 정렬했을 때 2개를 선택하면 된다.
- 참고로 P에 속한 숫자 집합의 양 끝에 대해서도 검사해주어야 한다. 범위 안에만 있다면 P1 - 1 과 Pn + 1 위치를 후보에 넣고 P1 - 1 그리고 K - Pn 을 미리 계산해준다.
- 예외 처리: Pi-1 과 Pi 사이에 숫자가 3개 이상 있을 때 홀수 개수이면 중간에 1개 숫자가 겹치므로 빼주어야 한다. 예를 들어 3 4 5 6 7 에서 3과 7이 P에 속할 때 4를 선택하면 4,5 해서 2점이고 6을 선택하면 5,6 해서 2점인데 여기서 큰 값 2개를 고르는데 후보가 4 와 6 밖에 없다면 5가 중복되니 가까운 c의 개수를 4와 6중에서 1개 빼주어야 한다. 후보가 무엇인지는 중요하지 않기 때문에 4,6을 선택하거나 4,X 또는 6,X 를 선택할 때 가까운 c의 개수는 정확하게 계산될 수 있다.
- 시간 복잡도는 O(N)
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#define pb push_back
#define sz(c) (int)(c).size()
using namespace std;
const static int _ = []() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
return 0;
}();
void solve() {
int N, K;
cin >> N >> K;
set<int> pset;
for (int i = 0, tmp; i < N; i++) {
cin >> tmp;
pset.insert(tmp);
}
vector<int> tickets(pset.begin(), pset.end());
vector<int> scores;
if (tickets.front() > 1) scores.pb(tickets[0]-1);
if (tickets.back() < K) scores.pb(K - tickets.back());
for (int i = 1; i < sz(tickets); i++) {
int diff = tickets[i] - tickets[i-1];
if (diff > 1) { // 사이에 숫자가 1개 이상 있을 때
scores.pb(diff >> 1); // 가까운 c의 개수 계산 (두 숫자의 차이 / 2)
if (diff > 2) { // 숫자가 2개 이상 있을 때
if ((diff-1) & 1) scores.pb((diff >> 1) - 1); // 홀수개이면 중복 제외
else scores.pb(diff >> 1); // 짝수개이면 중복이 없으므로 그대로 계산
}
}
}
// 내림차순 정렬
sort(scores.begin(), scores.end(), [&](int a, int b) { return a > b; });
int wins = 0;
// 최대 2개를 선택
for (int i = 0; i < min(2, sz(scores)); i++) wins += scores[i];
double ans = (double)wins / K;
ans = round(ans * 1e6) / 1e6;
cout << ans << endl;
}
int main() {
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
Roaring Years
- 문제 설명: 입력으로 년도가 주어질 때 다음 roaring 년도를 구하라.
- roaring 의 유무는 숫자가 연속되는 숫자로 이루어진 것을 의미한다.
2021 -> 20 / 21
78910 -> 7 / 8 / 9 / 10
99100 -> 99 / 100
778, 122, 2020 같은 경우는 해당되지 않는다.
- roaring 의 유무는 숫자가 연속되는 숫자로 이루어진 것을 의미한다.
- 입력
- Test Set 1: 1 <= Y <= 10^6
- Test Set 2: 1 <= Y <= 10^18
- 첫번째 접근법: Y가 작기 때문에 1씩 증가시켜서 roaring 인지 파악하는 것으로 해결할 수 있다. 연속되려면 시작 번호는 최대 전체 자릿수의 절반정도 차지해야 하므로 L/2 부터 1까지 숫자를 나누는 단위를 줄이면서 roaring인지 시도해볼 수 있다. 큰 단위로 나누어질수록 가장 가까운 숫자이기 때문이다. 주의할 점은 자릿수 올림이 발생할 수 있기 때문에 L만큼 단위를 나눴을 때 연속되지 않는다면 L+1만큼 단위를 나눠서 검사할 필요가 있다. 또한 숫자의 맨 앞에 0이 오는 경우 예외 처리를 해주어야 한다.
- 시간 복잡도: O(Y)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define sz(c) (int)(c).size()
using namespace std;
bool is_roaring(const string y, int l) {
int prev = stoi(y.substr(0, l)), curr = -1;
for (int i = l; i < sz(y); i += l, prev = curr) {
if (y[i] == '0') return false;
if (i+l > sz(y)) return false;
curr = stoi(y.substr(i, l));
if (prev + 1 == curr) continue;
if (i+l+1 > sz(y)) return false;
curr = stoi(y.substr(i, l+1));
if (prev + 1 == curr) {
l++;
continue;
} else return false;
}
return true;
}
void solve() {
string year;
cin >> year;
int next = stoi(year);
while (next++) {
string y = to_string(next);
for (int l = sz(y)>>1; l > 0; l--) {
if (is_roaring(y, l)) {
cout << next << endl;
return;
}
}
}
}
int main() {
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cout << "Case #" << tc << ": ";
solve();
}
return 0;
}- 두번째 접근법: Y의 범위가 10^18 이기 때문에 위의 방법대로 하면 시간 초과가 발생한다. 풀이 아이디어는 모든 roaring year의 집합에서 시작 번호를 이분법(bisection method)으로 찾는 것이다. 시작번호만 알면 뒤에 연속되는 자릿수에 따라 roaring year를 알 수 있기 때문에 시작번호만 이분법으로 탐색한다. 개인적으로 다른 사람 풀이를 봤을 때는 매개변수 탐색이라고 보는 것이 맞는 듯하다. 알고리즘은 다음과 같다.
- 최초 연속되는 숫자의 개수를 2부터 시작하고 한 자릿수일 때 10^18까지 검사하기 위해 최대 18개까지 이분법을 수행한다.
- 시작 번호는 10^18의 절반인 10^9가 최댓값이 되고 최솟값은 1이 된다. 이분 탐색으로 시작번호를 찾을 때는 시작번호로 만들어진 숫자가 입력 Y보다 크면 시작번호를 줄이고, Y보다 작거나 같으면 시작번호를 늘린다. 모든 집합의 원소에서 Y 다음으로 올 수 있는 가장 작은 값을 찾는 것이기 때문에 입력 Y보다 크면 시작번호를 줄여야 된다.
- 매 연속되는 숫자 개수(2~18)마다 이분법을 수행해서 찾은 roaring year 중 최솟값을 반환하면 된다.
- 시간 복잡도: O(log2(1e9) * 18 * 18) = 29.897352853986263 * 18 * 18 < 9,720
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define sz(c) (int)(c).size()
using namespace std;
typedef long long ll;
const ll INF = 2e18;
ll Y;
ll make_roaring_year(ll nbr, int num_consecutives) {
auto digits = [&](ll v) {
ll x = v, y = 1;
while (x) x /= 10, y *= 10;
return y;
};
ll ret = 0;
for (int i = 0; i < num_consecutives; i++, nbr++) {
ll d = digits(nbr);
// 이미 범위를 넘는 경우 roaring year은 없는 것이므로 INF를 반환한다.
if (ret > INF/d) return INF;
ret = ret * d + nbr;
ret = min(ret, INF);
}
return ret;
}
ll search(int num_consecutives) {
ll lo = 0, hi = 1e9;
while (lo + 1 < hi) {
ll mid = (lo + hi) >> 1;
if (make_roaring_year(mid, num_consecutives) > Y) hi = mid;
else lo = mid;
}
ll ret = make_roaring_year(hi, num_consecutives);
return ret;
}
void solve() {
cin >> Y;
ll ans = INF;
for (int n = 2; n <= 18; n++)
ans = min(ans, search(n));
cout << ans << endl;
}
int main() {
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
Double or NOTing
'Algorithm > Problem Solving' 카테고리의 다른 글
| Google Code Jam 2021 Round 1B (0) | 2021.04.26 |
|---|---|
| Google Code Jam 2021 Round 1A (0) | 2021.04.26 |
| [DFS, Tree] (프로그래머스 Lv 4) 매출 하락 최소화 (0) | 2021.04.24 |
| [구현] (프로그래머스 Lv 4) 블록 게임 (0) | 2021.04.24 |
| [PriorityQueue] (프로그래머스 Lv 3) 셔틀버스 (0) | 2021.04.24 |
