총 7개의 문제 중 쉬웠던 문제 A, B, C를 풀었습니다.
제일 쉬운 난이도인 Div 3에서도 기어다니는거보면 아직 갈 길이 먼 것 같습니다.
A: https://codeforces.com/contest/1077/problem/A
K가 짝수이면 개구리가 (a - b) * (K / 2)만큼 움직이고 K가 홀수이면 개구리가 (a - b) * (K / 2) + a 만큼 움직입니다.
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
long long t, a, b, k;
cin >> t;
while (t--)
{
cin >> a >> b >> k;
long long result = 0;
//K가 짝수 일 때
if (k % 2 == 0)
result += (a-b) * k/2;
//K가 홀수일 때
else
{
result += (a)*(k / 2 + 1);
result -= b * (k / 2);
}
cout << result << "\n";
}
return 0;
}
B: https://codeforces.com/contest/1077/problem/B
우선 전구의 상태를 입력을 받고 1 0 1 인 곳을 찾습니다.
그리디하게 마지막 1을 0으로 바꿔주며 1 0 1의 개수를 구하면 됩니다.
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 100;
int arr[MAX];
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i < N; i++)
cin >> arr[i];
int result = 0;
for (int i = 1; i < N - 1; i++)
//그리디하게 접근
if (!arr[i] && arr[i - 1] && arr[i + 1])
{
arr[i + 1] = 0;
result++;
}
cout << result << "\n";
return 0;
}
C: https://codeforces.com/contest/1077/problem/C
N이 최대 200,000이기 때문에 O(N^2)으로는 풀 수 없는 문제였습니다.
Ai = A0 + A1 + ... 가 되기 위해서는 Ai가 총합의 1/2여야 합니다.
따라서 저는 이분 탐색을 통해 Ai를 지웠을 때도 good array가 성립하는지 확인했습니다.
핵 당했습니다 ㅠㅠ
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 200000 + 1;
vector<pair<int,int>> v;
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
v.resize(N);
//총합을 구한다
long long sum = 0;
for (int i = 0; i < N;
i++)
{
cin
>> v[i].first;
sum
+= v[i].first;
v[i].second = i + 1;
}
sort(v.begin(),
v.end());
vector<int> result;
for (int i = 0; i < N;
i++)
{
//우선은 v[i]를 빼고
sum
-= v[i].first;
//이분 탐색 진행
int low = 0, high = N -
1;
while (low <= high)
{
int mid = (low + high)
/ 2;
if (mid != i
&& v[mid].first * 2 == sum)
{
result.push_back(v[i].second);
break;
}
else if (v[mid].first * 2 < sum)
low
= mid + 1;
else
high
= mid - 1;
}
//v[i]를 다시 더해준다
sum
+= v[i].first;
}
cout << result.size() << "\n";
for (int i = 0; i <
result.size(); i++)
cout
<< result[i] << " ";
cout << "\n";
return 0;
}
다행히 같은 학교 학우이신 Green55님(https://blog.naver.com/pasdfq/221400537747)가 잘 설명해주신 덕분에 왜 틀렸는지 알 수 있었습니다.
아래 코드는 Green55님의 설명을 토대로 작성한 코드입니다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int MAX = 200000;
long long N, arr[MAX], sum = 0;
int visited[1000000 + 1];
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
memset(visited, -1, sizeof(visited));
//visted[X] = -1: arr에 X가 없음
//visited[X] = N + 10: arr에 X가 두 개 이상 있음
//그 외: arr에서 X의 값을 가지는 원소의 인덱스
for (int i = 0; i < N; i++)
{
cin >> arr[i];
sum += arr[i];
if (visited[arr[i]] != -1)
visited[arr[i]] = N + 10;
else
visited[arr[i]] = i;
}
vector<int> result;
for (int i = 0; i < N; i++)
{
long long temp = sum - arr[i];
//A[i]가 좋으려면, A[i]를 지웠을 때
//A[j] = (A[i]와 A[j]를 제외한 모든 수의 합을 만족하는 j가 있어야함
//temp = (전체 합 - A[i])라고 하면, A[j] = temp/2인 j가 있는지 확인
if (temp % 2 == 0 && temp / 2 < (1000000 + 1) && visited[temp / 2] != -1 && visited[temp / 2] != i)
result.push_back(i + 1);
}
cout << result.size() << "\n";
for (int i = 0; i < result.size(); i++)
cout << result[i] << " ";
cout << "\n";
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~