-
유사코문제셋으로 공부를 해본다해본다 하다가 드디어 처음으로 문제를 풀어보았다.
처음이니 가볍게 브론즈부터 시작해야지 라고 생각했는데 내 실력을 너무 과대 평가한것같다.
생각보다 엄청 어려웠다.
체감상 난이도는 Farmer John Actually Farms < Candy Cane Feast < Cowntact Tracing 2 순서대로 어려웠다. 특히 2번문제는
못풀겠어서 중간에 에디토리얼을 봤다.
A : Candy Cane Feast
구현자체는 쉽지만 시간복잡도때문에 쉽게 손이 가지않는 문제다.
하지만 나이브하게 처리해도 시간안에 돌아간다는 사실을 증명한다면 구현은 어렵지않다.
나이브한 방법에서는 O(N * M) 시간이 소요될 수 있으며, 이는 최대 4 * 10^10의 연산량으로 시간 초과가 발생할 수 있다. 따라서 이를 해결하기 위한 시간 최적화 방법을 고려해야 한다.
1. 각 소의 앞에 있는 소들이 자신보다 크면, 그 소는 더 이상 먹을 수 없기 때문에 그 경우는 고려할 필요가 없다. 이는 불필요한 계산을 줄이는 중요한 최적화 포인트이다. 즉, 앞에 있는 소가 자신보다 크다면 더 이상 먹는 행위를 할 수 없으므로 그 경우는 제외해야 한다.
2. 첫 번째 소가 중요한 역할을 한다. 첫 번째 소가 cane(막대기)을 모두 먹을 수 있다면, 이후의 소들에 대해서는 굳이 복잡한 처리를 할 필요가 없다. 만약 첫 번째 소의 키보다 cane이 작다면, 첫 번째 소가 그 cane을 먹고 크기가 커지게 된다.
첫 번째 소의 크기가 커지면 이후 cane들을 모두 처리할 수 있으므로, 나머지 소들은 나이브하게 처리해도 시간 복잡도에 큰 영향을 미치지 않는다.
특히 첫 번째 소가 cane를 먹을 때마다 두 배로 커지도록 설정하면, 첫 번째 소가 30번 정도 cane를 먹으면 그 크기가 매우 커져, 모든 cane보다 커질 수 있다. 이 경우 첫 번째 소만 제대로 처리하면, 다른 소들에 대한 처리 역시 매우 간단해진다.
결론적으로, 첫 번째 소의 크기를 적절히 키우는 방식으로 나머지 소들에 대한 처리를 간소화할 수 있으며, 이를 통해 전체 시간 복잡도를 크게 줄일 수 있다.<소스코드>
#include <stdio.h> #include <algorithm> #include <vector> using namespace std; using ll = long long; int n, m; vector <pair<ll, int>> cow; vector <ll> cane, ans; ll first_cow; int main() { int i, j; scanf("%d %d", &n, &m); ll now_cow = -2e9; for(i=0;i<n;i++) { ll x; scanf("%lld", &x); if(now_cow < x) { cow.push_back({x, i}); //소의 키, 인덱스 저장 now_cow = x; } ans.push_back(x); } first_cow = cow[0].first; for(i=0;i<m;i++) { ll x; scanf("%lld", &x); cane.push_back(x); } for(i=0;i<m;i++) { ll now = cane[i]; ll tall = 0; if(now <= first_cow) { first_cow += now; continue; } else { tall = first_cow; first_cow *= 2; } for(j=1;j<cow.size();j++) { int idx = cow[j].second; ll h = ans[idx]; if(h > tall) { if(h >= now) { ans[idx] += (now - tall); break; } else { ll imsi = ans[idx]; ans[idx] += (ans[idx] - tall); tall = imsi; } } } } printf("%lld\n", first_cow); for(i=1;i<ans.size();i++) { printf("%lld\n", ans[i]); } return 0; }
B : Cowntact Tracing 2
접근법은 비슷했지만, 생각이 정답에 다다르지 못했다. 조금 더 고민했다면 답을 찾았을지도 모르겠다. 에디토리얼을 너무 일찍 본 게 아닌가 하는 생각이 든다.
경우를 나누는 방식은 나와 비슷했다. 하지만 최대일수를 구할 필요는 없었다.
나는 일수와 초기 감염된 소 사이의 상관관계를 잘못 계산한 것 같다. 물론, 사실 상관관계 같은 건 따로 구할 필요가 없다.
단순히 최소한의 소들이 포함된 연속된 구간의 길이를 구하고, 이를 하루 동안 전파할 수 있는 거리로 나누어 처리하면 되는 문제였다.
결국 쓸데없는 삽질을 너무 많이 한 셈이다.
먼저 인접한 1들을 하나의 덩어리로 보고, 각 덩어리의 1의 수를 저장한다. 이를 '소 무리'라고 하자.
소 무리 중에서 감염에 가장 빨리 걸릴 수 있는, 즉 가장 작은 무리를 찾아야 한다. 이때 양쪽 끝에 있는 소들은 따로 처리해야 한다. 벽에 붙어 있는 소는 다른 소에게 감염을 퍼뜨릴 수 없기 때문이다. 양쪽 끝의 소들을 일반적인 무리로 바꾸어 생각하면, (소 무리의 수 * 2 - 1)만큼의 무리와 같다고 볼 수 있다.
또한, 소 무리가 짝수인지 홀수인지에 따라 감염 방식이 달라진다. 예를 들어, 소가 4마리면 1마리로는 4마리를 모두 감염시킬 수 없기 때문에, 2마리부터 시작해야 한다. 그래서 소 무리가 짝수일 경우는 -1을 해줘야 한다.
이 모든 경우를 적절히 처리하면 문제에서 100점을 받을 수 있다.<소스코드>
#include <stdio.h> #include <algorithm> #include <vector> using namespace std; int n; int arr[300010]; vector<int> vec; int main() { int i, j; scanf("%d", &n); for(i=0;i<n;i++) scanf("%1d", &arr[i]); int now_num = arr[0]; int count = 0; if(now_num == 1) count++; for(i=1;i<n;i++) { if(arr[i] == 0) { if(now_num == 1) { vec.push_back(count); count = 0; now_num = 0; } else { count = 0; } } if(arr[i] == 1) { now_num = 1; count++; } } if(count > 0) vec.push_back(count); int min_edge = 2e9; int vsz = vec.size(); int st = 0, ed = vsz; if(arr[0] == 1) { min_edge = min(min_edge, vec[0] * 2 - 1); st++; } if(arr[n - 1] == 1) { min_edge = min(min_edge, vec[vsz - 1] * 2 - 1); ed--; } int min_odd = 2e9; // 홀수 min int min_even = 2e9; //짝수 min for(i=st;i<ed;i++) { if(vec[i] % 2) { min_odd = min(min_odd, vec[i]); } else { min_even = min(min_even, vec[i]); } } int Day = min(min_edge, min(min_odd, min_even - 1)); int ans = 0; for(i=0;i<vsz;i++) { ans += (vec[i] + Day - 1) / Day; //올림을 위해 더함 } printf("%d", ans); return 0; }
C : Farmer John Actually Farms
2023 December에 있는 문제중에 가장 쉬운 문제인것같다.
그냥 직관적으로 세운 풀이로 풀렸다.
3번째에 주어지는 배열을 가지고 오름차순 정렬후 로직을 나누어 처리하면 된다.
3번째 주어지는 배열이 겹치는 경우는 없음으로 예외처리가 생각보다 간단하다.
a, b, t라하면
a = 초기 식물
b = 하루에 얼마나 크는지
t = 결과적으로 자신보다 큰 식물의 수
라 해보자.
이때 t를 오름차순으로 정렬하면 최종 길이의 내림차순으로 정렬한 것과같다.
따라서
a[i] < a[i + 1]
b[i] > b[i + 1]
꼴이라면 몇일이지나야 조건을 만족하는지 조사하고
반대라면 몇일이 지나면 조건을 만족하지 못하는지를 조사해서
연립하면 끝난다.
t가 겹치는 경우를 생각해서 쓸데없이 시간을 날렸다.#include <stdio.h> #include <algorithm> #include <vector> using namespace std; using ll = long long; struct dat { ll a, b, t; }; bool comp(dat x, dat y) { return x.t < y.t; } dat arr[200010]; int n; int main() { int t; scanf("%d", &t); while(t--) { int i, j; int ansch = 0; scanf("%d", &n); for(i=0;i<n;i++) scanf("%lld", &arr[i].a); for(i=0;i<n;i++) scanf("%lld", &arr[i].b); for(i=0;i<n;i++) scanf("%lld", &arr[i].t); if(n == 1) { if(arr[0].t == 0) { printf("0\n"); continue; } else { printf("-1\n"); continue; } } sort(arr, arr + n, comp); ll min_val = 0, max_val = 2e15; for(i=0;i<n - 1;i++) { if(arr[i].t == arr[i + 1].t) continue; if(arr[i].a < arr[i + 1].a && arr[i].b > arr[i + 1].b) { min_val = max(min_val, ((arr[i + 1].a - arr[i].a) + (arr[i].b - arr[i + 1].b)) / (arr[i].b - arr[i + 1].b)); } if(arr[i].a > arr[i + 1].a && arr[i].b < arr[i + 1].b) { if((arr[i].a - arr[i + 1].a) % (arr[i + 1].b - arr[i].b) == 0) { max_val = min(max_val, (arr[i].a - arr[i + 1].a) / (arr[i + 1].b - arr[i].b) - 1); } else max_val = min(max_val, (arr[i].a - arr[i + 1].a) / (arr[i + 1].b - arr[i].b)); } if(arr[i].a <= arr[i + 1].a && arr[i].b <= arr[i + 1].b) { ansch = 1; break; } } if(max_val < min_val || ansch == 1) { printf("-1\n"); continue; } if(ansch == 1) { printf("-1\n"); continue; } printf("%lld\n", min_val); } return 0; }비록 브론즈지만 난이도도 적당하고 재밌었다.
백준에 USACO가 올라와있어 생각날때마다 풀어볼것같다.