2021. 10. 14. 16:20ㆍ알고리즘/codeforce
1. A
- 간단한 수학 문제
- 세개의 숫자중 가장큰것에서 +1 해주면된다
- 이때 가장 큰 수가 유일한 한 값이라면 0을 출력해주는 예외처리만 해주면된다.
while (T--)
{
int maxC;
int A[3];
cin >> A[0] >> A[1] >> A[2];
maxC = max(A[0], max(A[1], A[2]));
map<int, int> dic;
for (int i = 0; i < 3; i++)
{
dic[A[i]]++;
}
int a[3];
for (int i = 0; i < 3; i++)
{
a[i] = maxC - A[i];
a[i]++;
if (dic[maxC] == 1 && a[i] == 1)
{
a[i]--;
}
}
cout4(a[0], " ", a[1], " ");
cout2(a[2], " \n");
}
2. B
- 구현문제
- 25로 나누어지는 수를 만들어야하는데
- 이때 일의자리와 십의자리수만 보면된다
- 끝 두자리로 "25", "50", "75" , "00" 이 와야 25로 나눌 수 있기 때문
- 그러므로 문자열로 입력을 받고, 앞에서부터 인덱스를찾아 몇개를 제외시켜야하는지 계산 후
- 가장 작은 값을 출력한다.
반성: 하드코딩으로 문제를 해결하려다가 꼬이고 꼬여 틀렸다. |
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
while (T--)
{
string a;
cin >> a;
reverse(a.begin(), a.end());
int answer[4] = {1111, 1111, 1111, 1111};
map<int, vector<int>> dic;
for (int i = 0; i < a.size(); i++)
{
dic[a[i] - '0'].push_back(i);
}
pair<int, int> find[] = {{2, 5}, {5, 0}, {7, 5}, {0, 0}};
for (int i = 0; i < 4; i++)
{
auto [s, f] = find[i];
if ((dic[f].size() > 0 && dic[s].size() > 0) || (dic[f].size() > 1 && f == 0 && s == 0))
{
int ff = dic[f][0];
auto ss = lower_bound(dic[s].begin(), dic[s].end(), ff + 1);
if (ss != dic[s].end())
{
answer[i] = ff + (*ss - ff - 1);
}
}
}
cout << *min_element(&answer[0], &answer[0] + 4) << "\n";
}
}
3. C
- 그리디 + 정렬 + 이진검색
- 가장 많은 쥐를 탈출시켜야한다.
- 한턴에 한번씩 쥐를 한마리만 움직일 수 있다.
- 이때 최대한 많이 탈출시키는것.
- 가장 구멍과 가까운 쥐들을 포함시키는것이 최대가된다.
- 그렇지 않은 경우에서 답이나왔다고 가정해보면,
- 선택한 한마리를 가장 구멍과 가까운쥐들로 교체해도 손해는 없음을 알 수 있다.
- 그러므로 쥐들을 정렬하고, 이진 검색으로
- 구멍에서 mid번째 쥐부터시작해서 n번째 쥐 까지 전부 탈출가능한지를 조사해야한다.
반성 : 이진 검색을 잘못 설정하여 한번 틀렸다. => https://www.acmicpc.net/blog/view/109 |
bool go_hole(int idx)
{
int cat = 0;
for (int i = idx; i < m.size(); i++)
{
if (cat >= m[i])
{
return false;
}
cat += (n - m[i]);
}
return true;
}
int bisearch()
{
int lo = 0, hi = m.size() - 1;
int mid = 0;
while (lo != hi)
{
mid = (lo + hi) / 2;
if (go_hole(mid))
{
hi = mid;
}
else
{
lo = mid + 1;
}
}
return m.size() - hi;
}
4. D1
- GCD 문제
- 주어진 배열에서 가장 최소값과 나머지와의 차이들을 계산하여
- 이들의 최대 공약수를 구하는 문제.
- 주의해야할점은 차이들의 최대 공약수가 0일때, 즉 모든 값들이 같을 때 -1 처리해줘야한다
반성: 차이가 0일때 0을 출력하게했다. |
int gcd(int x, int y)
{
if (y == 0)
{
return x;
}
else
{
return gcd(y, x % y);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
map<int, int> dic;
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
dic[a]++;
}
if (dic.size() >= 2)
{
auto before = dic.begin();
int min1 = before->first;
int min2 = next(dic.begin(), 1)->first;
int answer = abs(min1 - min2);
for (auto it = next(dic.begin(), 2); it != dic.end(); it++)
{
int b = abs(it->first - min1);
answer = gcd(answer, b);
before = it;
}
cout << answer << "\n";
}
else
{
cout << -1 << "\n";
}
}
}
5. D2
?
6. E
- BFS 문제
- 주어진 트리에서 간선이 1개인 노드들을 전부 없애는것
- 이런 제거를 k 번 했을 때 남아있는 노드들의 개수를 구하는 문제이다.
- bfs에서 시작점을 "잎"노드들로 설정하여 문제를 해결하였다.
- 즉, queue 에 "잎"노드들을 담아,
- 잎과 연결된 간선을 제거하면서,
- 연결된 노드가 잎이되는지 검사한 후
(set 을 사용해서 간선을 제거하고 잎이되는지 검사하였다.)
- 잎이되면 queue에 삽입하도록 하였다.
vector<set<int>> adjList;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
while (T--)
{
int n, k;
cin >> n >> k;
adjList.clear();
adjList.resize(n);
queue<pair<int, int>> q;
// 입력
for (int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
a--;
b--;
adjList[a].insert(b);
adjList[b].insert(a);
}
// 잎들을 queue에 넣는다.
for (int i = 0; i < n; i++)
{
if (adjList[i].size() <= 1)
{
q.push({0, i});
}
}
int answer = 0;
// bfs
while (!q.empty())
{
auto [d, here] = q.front();
q.pop();
// K번째에 도달
if (d == k)
{
break;
}
answer++;
// 만약 간선이 0 인 노드이면 계속 계산할 필요가 없다.
if (adjList[here].size() == 0)
{
answer = n; // 두개의 노드들만 있을 경우 노드 한개가 큐에 두번들어가게된다.
continue;
}
int b = *adjList[here].begin();
adjList[b].erase(here);
if (adjList[b].size() <= 1)
{
q.push({d + 1, b});
}
}
cout << n - answer << "\n";
}
}
'알고리즘 > codeforce' 카테고리의 다른 글
[codeforces] Educational Codeforces Round 115 (Rated for Div. 2) A,B,C (0) | 2021.10.11 |
---|---|
[codeforces] Codeforces Round #744 (Div. 3) (0) | 2021.09.30 |