본문 바로가기

728x90
반응형

CP

Atcoder Beginner Contest 206 (ABC 206) 풀이 A. Maxi-Buying 단순 계산 문제이다. N을 입력받고, 1.08*N을 정수단위로 올림 했을 때 206과 대소 비교하는 문제이다. #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); double n; cin >> n; n *= 1.08; int ans = (int)n; if (ans == 206) cout = n) { cout > n; map mp; for (int i = 0; i < n; i++) { int a; cin >> a; mp[a]++; } ll ans = 0; for (auto [a, b] : mp) { ans += 1LL * b * (..
Google Kickstart Round A 2021 풀이 Rank = 861 (KR 37) 1. K-Goodness String (12 pts) 길이가 N인 문자열 S가 주어지고, 각 글자를 원하는 만큼 변경할 수 있다. 1≤i≤N/2 인 i에 대해서 S[i] != S[N-i+1]인 i의 개수가 K가 되기 위한 최소 변경 횟수를 구하는 문제이다. 단순 구현 문제이다. S[i]나 S[N-i+1] 둘 중 하나를 바꾼다면 상태를 바꿀 수 있으니 처음 문자열에서 S[i] != S[N-i+1]인 i의 개수를 구한 다음 K와의 차이만큼 문자를 바꿔주면 된다. (멍청하게도 S[i] == S[N-i+1]이면 점수를 얻는다고 생각해서 1WA를 받았다. 왜 하필 예제 답이 같아서...) [소스 코드] #include using namespace std; int main(void..
[Codeforces] Round #709 (div. 2) A ~ D 풀이 2021.03.21 22:20 ~ 00:35 본 라운드 참여 (performance = 1844) 테크노컵은 뭔가 항상 어려운 느낌이다... 생각보다 퍼포먼스가 나쁘지 않게는 나왔는데, 개인적으로 요즘 코포 폼이 조금 올라왔다고 생각해서 더 아쉬운 기분이 든다. A. Prison Break (*800) 모든 칸들에서 밖으로 나갈 수 있기 위해서 제거해야 하는 벽의 수의 최소를 구하는 문제이다. 답은 가로 * 세로, 즉 칸의 개수이고 대회중에는 직관적으로 빠르게 해결했다. 정확한지는 모르겠으나 증명을 하자면, 각 칸마다 해당 칸에서 시작해서 밖으로 나갈 수 있는지 없는지를 상태로 표현하고, 벽이 제거된 이웃한 칸은 하나의 칸으로 합쳐진다고 생각하자. 벽을 하나 제거했을 때 밖으로 나갈 수 없었던 2개 이상..
[Codeforces] Round #559 (Div. 2) A ~ E 풀이 21.03.05 23:35 virtual 참가 / performance = 2391 A. A pile of stones (*800) +가 주어질 때는 돌이 1개 증가하고, -가 주어질 때는 돌이 1개 감소한다. 처음에 보유할 수 있는 돌은 임의로 정할 수 있고, 중간에 돌이 0개일 때 -가 들어오면 안 될 때, 최종적으로 가능한 최소 돌의 개수를 구하는 문제이다. 처음의 돌 수를 직접 정할 수 있으므로, 단순하게 -가 들어오는 경우, 만약 현재 돌이 0개이면 그대로 유지시켜주면 된다. 이 과정이 결국 처음의 돌 수를 1개 증가시키는 과정과 동일하다. [소스 코드] #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin..
[Codeforces] Round #694 (Div. 2) 풀이 2021. 01. 05 23:35 본 라운드 참가 실력이 정체되어있다. 예전엔 더 올라갈 수 있는데 운이 안 따라주는 느낌이었다면 지금은 느낌이 좀 다르다.... 재활이 꽤 오래 걸릴 것 같다. 1471A. Strange Partition 주어진 배열에서 인접한 두 원소를 대신해서 두 원소의 합으로 대체할 수 있다. 배열의 원소는 1개만큼 줄어든다. 이 연산을 원하는 만큼 한 후에, 배열의 각 원소를 x으로 나눈 값을 올림 하여 모두 더한 합의 최솟값과 최댓값을 구해야 한다. 최대인 경우는 연산을 한번도 하지 않은 원래의 배열에서 합을 구해주는 경우이고, 최소인 경우는 연산을 n-1번 적용한, 즉 배열의 원소가 1개만 남았을 때이다. [소스 코드] #include using namespace std; u..
[Codeforces] Round #551 (Div. 2) A ~ D 풀이 2021.01.03. 15:00 virtual 참가 / performance = 1563 [풀이] 1153A. Serval and Bus (*1000) 버스별로 정류장에 처음 도착하는 시간과 배차간격이 주어질 때, 버스정류장에 t초에 도착했을 때 제일 먼저 탈 수 있는 버스를 구하는 문제이다. 처음에 A번치고 생각보다 까다로웠으나, n이 100이고 t가 10만이기 때문에 각 버스별로 정류장에 도착하는 시간을 모두 구해줘도 무방하다. 나는 priority_queue를 이용하여 현재 pq에 담겨있는 버스들의 도착 시간 중에 제일 빠른 것을 확인해서, t보다 작다면 배차간격만큼 더해줘서 다시 넣어주고, 처음으로 t보다 큰 값이 나온 경우에 출력을 해주었다. #include using namespace std;..
Atcoder Beginner Contest 185 (ABC 185) 풀이 [문제 링크] atcoder.jp/contests/abc185 AtCoder Beginner Contest 185 - AtCoder AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp [풀이] A. ABC Preparation 각 점수별로 문제 수가 나와있고, 하나의 문제 set을 만들기 위해서는 점수별로 하나씩 문제가 필요하다. 따라서 네 정수 중 최솟값을 출력하면 된다. #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(n..