저저번주쯤 주말에 올해 2020년의 첫 킥스타트 라운드 A가 있었는데, 아무것도 모르고 주말에 잠을 퍼질러 자다가 참여를 못하게 되었다.
A라운드는 근데 문제 난이도가 낮아서 빨리풀기 대회였다니 뭐 이런이야기들을 들었는데, 대회 당시에는 참여를 못했지만 나중에 업솔빙이라도 해볼 겸 시간 날때 풀어보았다.
이번해의 킥스타트는 저번과는 다르게 Large dataset도 제출한 뒤 바로 full-feedback을 준다고 한다. 맞았는지 틀렸는지를 바로 알려준다는 것은 뭔가 좋은 것 같으면서도 안 좋은것 같기도 하다.
바로 한번 문제 풀어보도록 하겠다.
문제들은 여기에서 확인하고 다시 풀어볼 수 있다.
총 4문제가 있다. 정답률을 보니 난이도가 왼쪽 < 오른쪽 문제로 가는 것 같다.
1. Allocation
문제는 간단하다. N개의 집이 있고, 각각의 집의 가격은 Ai원이다. 그리고 총 B달러가 있을때 가장 많은 집을 사고 싶다고 한다. 몇개를 살 수 있는가?
그냥 Ai를 오름차순으로 소팅한 뒤 예산을 넘지 않는 만큼만 진행하면 된다. //(O(NlgN)//)로 풀리며, N이 //(10^5//)이므로 쉽게 풀린다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int A[100005];
void solve() {
int N, B;
cin >> N >> B;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
sort(A, A + N);
int ans = 0;
for (int i = 0; i < N; i++) {
if (B >= A[i]) {
B -= A[i];
ans++;
}
else {
break;
}
}
printf("%d\n", ans);
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
2. Plates
접시를 골라서 그 값들을 최대로 해야하는데, 접시는 위에서부터 연속된 것들만 고를 수 있다. 접시를 고르는 총 개수도 정해져있다.
dp문제인데, 맨처음에 dp인 것 같다가 시간복잡도가 안될 것 같았다는 생각이 좀 들어서 약간 긴가민가 했었다. 근데 문제를 부분문제로 나눌 수 있고 독립되게 풀린다는 것이 보여서 dp가 맞는 듯 했다.
2차원 dp로 풀 수 있는데 각 항의 정의는 다음과 같다.
//(dp[i][j]//)는 i번째 줄까지 쭉 진행했을 때, j개의 접시를 골라서 낼 수 있는 최대 점수
이러면 //(dp[i][j]//)를 이용해서 다음 줄에서 k개의 접시를 구하는 경우//(dp[i+1][j+k]//)를 쉽게 구할 수 있다.
for-loop를 돌리는 식으로 구현해보았다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[55][33];
int dp[55][1505]; //dp[i][j]는 i번째 라인까지 j개의 plate를 골라서 얻을 수 있는 최대 점수.
void solve() {
int N, K, P;
cin >> N >> K >> P;
memset(dp, 0, sizeof(dp));
memset(a, 0, sizeof(a));
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K; j++) {
cin >> a[i][j];
a[i][j] += a[i][j - 1];
}
}
for (int i = 1; i <= K; i++) {
dp[1][i] = a[1][i];
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= i * K; j++) {
for (int k = 0; k <= K; k++) {
dp[i + 1][j + k] = max(dp[i + 1][j + k], dp[i][j] + a[i + 1][k]);
}
}
}
printf("%d\n", dp[N][P]);
return;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
3. Workout
이거는 증가하는 수열에서 인접한 수열 사이의 차이를 일정 값 이하로 만들고 싶은 상황이다. 이 때 수열 사이 사이에 임의의 값을 갖는 녀석을 끼워넣을 수 있다. 이 때 인접한 수열 사이의 차이값의 최소값을 구하는 그런 문제이다.
최소값 구하는 문제, 최대값 구하는 문제 중 이러한 류의 문제들, 차이값의 최소 와 같은 좀 복잡한 값의 최소/최대문제는 보통 결정문제로 변경해서 푸는 파라메트릭 서치 문제이다.
인접한 값의 차이를 d 이하로 만들 수 있는가? 의 결정 문제로 바꾼 뒤 이녀석을 통해서 binary search를 돌리면 풀린다.
그리고 이 결정 문제는 보통 그리디나 선형 시간복잡도로 풀리게 된다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int M[100005];
int N, K;
bool ok(int v) {
int k = K;
for (int i = 1; i < N; i++) {
int diff = M[i] - M[i - 1];
k -= (diff + v - 1) / v - 1;
}
return k >= 0;
}
int solve() {
cin >> N >> K;
for (int i = 0; i < N; i++) {
cin >> M[i];
}
int l = 1;
int r = 1e9;
while (l < r) {
int m = (l + r) / 2;
if (ok(m)) {
r = m;
}
else {
l = m + 1;
}
}
return r;
}
int main() {
int tc;
cin >> tc;
for (int t = 1; t <= tc; t++) {
cout << "Case #" << t << ": " << solve() << endl;
}
}
4. Bundling
문자열들을 같은 크기의 Group들로 균일하게 나눈 뒤, 그 그룹들의 Longest prefix의 길이만큼 점수를 얻는데 이 점수를 최대화하는 그런 문제이다. 그룹을 어떻게 나눌 것인가까지는 알 필요 없이 점수만을 계산할 수 있다고 한다. 맨처음 이 문제를 보고 문자열 그냥 소팅한 뒤 K개씩 그룹핑 하면 되지 않을까 했는데 조금 생각해보니 바로 반례가 나왔다..
K가 만약 3이라고 하면 문자열이 다음과 같이 나왔을때 그리디하게 하면 최적화되지 않은 그룹핑이 된다.
A A A B C C C D E E E F
이런 경우 하나씩만 있는 B, D, F는 어차피 점수를 낼 수 없으므로 자기내들끼리 묶여서 남에게 피해를 주지 않아야 하는데 greedy하게 묶으면 망한다.
솔루션을 보니, Trie를 구축한 뒤, Trie Node별로 나타난 횟수를 체크해놓고, 나타난 횟수를 A라고 할때 각 노드별 floor(A/K)를 더하면 된다고 한다.
A % K에 해당하는 K개가 되지 못한 그룹녀석들은 어차피 어디에 끼여도 점수를 낼 수 없으므로 버리게 된다.
조금 생각해보니 correct한 알고리즘인 것이 이해가 되었다.
Trie는 malloc으로 구현하는 것이 귀찮아서 배열을 두고 정적할당과 같은 테크닉으로 구현을 해 보았다.
그리고 dfs로 모든 노드를 순회하면서 점수를 계산했다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 2000006
class Node {
public:
char c;
int num;
int next[28];
Node() {
clear();
}
void clear() {
memset(next, 0, sizeof(next));
num = 0;
c = 0;
}
};
Node nodes[MAXN];
int cnt;
int dfs(int v, int k) {
auto& cnode = nodes[v];
int ret = cnode.num / k;
for (char c = 'A'; c <= 'Z'; c++) {
if (cnode.next[c - 'A'])
ret += dfs(cnode.next[c - 'A'], k);
}
return ret;
}
int solve() {
int n, k;
cin >> n >> k;
//clear prev data
for (int i = 0; i <= cnt; i++) {
nodes[i].clear();
}
cnt = 0;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int ptr = 0;
for (char c : s) {
auto& next = nodes[ptr].next[c - 'A'];
if (!next) {
next = ++cnt;
nodes[next].c = c;
}
ptr = next;
nodes[ptr].num++;
}
}
return dfs(0, k);
}
int main() {
int tc;
cin >> tc;
for (int t = 1; t <= tc; t++) {
cout << "Case #" << t << ": " << solve() << endl;
}
}'알고리즘 & Problem Solving' 카테고리의 다른 글
| Google Codejam Kickstart 2020 Round B 후기 (0) | 2020.04.22 |
|---|---|
| Google Codejam 2020 Qualification Round 후기 (0) | 2020.04.05 |
| 백준 1854번 K번째 최단경로 찾기 문제 풀이 (0) | 2020.02.26 |
| 백준 1753번 문제 '최단경로' 풀이 (0) | 2020.02.26 |
| 백준 1087번 문제 쥐잡기 풀이 (0) | 2020.02.18 |
