알고리즘/codeforce

Codeforces Round #521 (Div. 3)

꾸준함. 2018. 11. 17. 02:11

총 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


지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형