최근 본 대회/코테 중에 제일 쉬웠다. 올 초에 쇼미더코드를 봤을 때 너무 쉬워서 좀 너무하다 싶었었는데... 그거보다 더 쉽다.
작년에 조금 어려웠다는 얘기를 듣기도 했고, 코테 시간이 굉장히 짧아서 한번 실수하면 쭉 밀리기 때문에 긴장했었는데, 괜히 긴장했다.
120분 시험시간에 40분만에 다 풀고 30분 샤워하고 밥먹었다.
문제는 유출 금지라는 사항이 있어서 풀이 코드만 첨부하겠다.
결과적으로 코테/서류 에서 떨어졌다. 코테 문제는 100% 다 맞춘 코드라 자신이 있기 때문에 서류에서 떨어진 것 같은데... 좀 개판이긴 했지만 아쉽긴하다.
1번
전형적인 코테 1번 문제. string 파싱해서 map으로 넣은 뒤 조건에 따라 처리해주면 된다.
중복때문에 map<string, set<string>>으로 처리했었는데, map이랑 set을 같이 쓰는게 불-편해서 map으로 string 해싱해서 index기반으로 처리해주는 코드로 고쳤다.
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
os << pai.first << ' ' << pai.second;
return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
is >> pai.first >> pai.second;
return is;
}
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
#define all(x) x.begin(), x.end()
#define INF (INT_MAX / 2)
#define MAX_N 105
#define MAX_CHAR 26
#define MOD 1'000'000'007
#define MOD2 1'000'000'009
vector<string> solution(vector<string> logs) {
vector<string> answer;
map<string, int> problemMapper;
int pmCnt = 0;
map<string, int> userMapper;
int uCnt = 0;
for (string& s : logs) {
int idx = s.find(' ');
string user = s.substr(0, idx);
string problem = s.substr(idx + 1, s.size() - idx - 1);
if (userMapper.find(user) == userMapper.end()) {
userMapper.emplace(user, uCnt++);
}
if (problemMapper.find(problem) == problemMapper.end()) {
problemMapper.emplace(problem, pmCnt++);
}
}
bool solved[MAX_N][MAX_N];
for (string& s : logs) {
int idx = s.find(' ');
string user = s.substr(0, idx);
string problem = s.substr(idx + 1, s.size() - idx - 1);
solved[problemMapper[problem]][userMapper[user]] = true;
}
for (auto& p1 : problemMapper) {
int cnt = 0;
for (auto & p2 : userMapper) {
cnt += solved[p1.second][p2.second];
if (solved[p1.second][p2.second]) {
cout << make_pair(p1.first, p2.first) << endl;
}
}
if (cnt >= (uCnt + 1) / 2) {
answer.emplace_back(p1.first);
}
}
return answer;
}
#ifndef ONLINE_JUDGE
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
return 0;
}
#endif
2번
역시 전형적인 dp문제. O($n^2$)에 간단하게 풀린다.
dp[i] = 밧줄이 i개있을때 최소 비용
로 정의하면 쉽게 풀린다. 솔직히 풀이할 게 없다.
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
os << pai.first << ' ' << pai.second;
return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
is >> pai.first >> pai.second;
return is;
}
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
#define all(x) x.begin(), x.end()
#define INF (INT_MAX / 2)
#define MAX_N 2005
#define MAX_CHAR 26
#define MOD 1'000'000'007
#define MOD2 1'000'000'009
int dp[MAX_N];
int getDp(int idx, int n, vector<int>& times) {
if (idx == n) {
return 0;
}
int& ret = dp[idx];
if (ret != -1) {
return ret;
}
ret = INT_MAX;
for (int i = 0; i < min((int)times.size(), idx); ++i) {
if (idx + i + 1 > n) {
break;
}
ret = min(ret, getDp(idx + i + 1, n, times) + times[i]);
}
return ret;
}
int solution(int n, vector<int> times) {
memset(dp, -1, sizeof(dp));
int answer = getDp(1, n, times);
return answer;
}
#ifndef ONLINE_JUDGE
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
return 0;
}
#endif
3번
그리디.
모든 로켓에게 최소 연료를 1공급해야하기 때문에 먼저 모든 로켓에 1만큼만 분배한다.
그 이후, 연료를 1 공급할 때 마다 속력이 증가하기 때문에 가장 시간이 오래 걸리는 로켓에게 1을 분배하고, 걸리는 시간을 다시 계산한다.
연료를 다 쓸 때 까지 계속 가장 시간이 오래걸리는 로켓에게 1씩 분배하면 된다.
걸리는 시간기준으로 maxheap에 넣어두면 O($logn$)이 되므로 O($flogn$)에 풀린다.
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
os << pai.first << ' ' << pai.second;
return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
is >> pai.first >> pai.second;
return is;
}
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
#define all(x) x.begin(), x.end()
#define INF (INT_MAX / 2)
#define MAX_N 2005
#define MAX_CHAR 26
#define MOD 1'000'000'007
#define MOD2 1'000'000'009
struct Data {
double time;
int idx;
int fuel;
Data(double time, int idx, int fuel) {
this->time = time;
this->idx = idx;
this->fuel = fuel;
}
};
struct compare {
bool operator() (const Data& d1, const Data& d2) {
return d1.time < d2.time;
}
};
int solution(int fuel, vector<int> powers, vector<int> distances) {
int n = powers.size();
priority_queue<Data, vector<Data>, compare> pq;
for (int i = 0; i < n; ++i) {
distances[i] *= 2;
powers[i] *= 2;
}
fuel -= n;
for (int i = 0; i < n; ++i) {
int remain = distances[i] - (powers[i] / 2);
double time = (double)remain / powers[i] + 1;
pq.emplace(time, i, 1);
}
while(fuel) {
--fuel;
int i = pq.top().idx;
int dfuel = pq.top().fuel + 1;
//cout << pq.top().idx << ' ' << pq.top().time << ' ' << pq.top().fuel << endl;
pq.pop();
int remain = (distances[i] - (powers[i] / 2 * dfuel * dfuel));
double time = (double)remain / (powers[i] * dfuel) + dfuel;
pq.emplace(time, i, dfuel);
}
int answer = ceil(pq.top().time);
return answer;
}
#ifndef ONLINE_JUDGE
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cout << solution(8, {20, 30}, {750, 675}) << endl;
return 0;
}
#endif