알고리즘 공부 (2024_11_15)

 

 

백준 2923 : 숫자게임

아 이문제는 진짜 너무 아쉽다. 풀어놓고 아 근데 이거 타임오버같은데..이게 아닌거같아 하면서 결국 코드도 안적어보고 블로그 뒤져봤다.

https://studykty.tistory.com/217

이걸 틀리네. 풀이도 똑같더라.

결국 이게 0인값도 있고, 했던건 지워지기 때문에 n^2 까지 안가는거 같아 보이더라.

아쉬움.

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <fstream>
#include <stack>
#include <math.h>
#include <string>
#include <climits>

using namespace std;

#define MAX 101
int n, arr[MAX], brr[MAX], result, mx, mn;

int main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        arr[a]++;
        brr[b]++;
    vector<int> v1(MAX), v2(MAX);
    for (int j = 0; j < MAX; j++) {
        v1[j] = arr[j];
        v2[j] = brr[j];
    }

    result = 0, mx = 100, mn = 1;
    while (mx >= 1 && mn < MAX) {
        while (mx >= 1 && v1[mx] == 0) {
            mx--;
        }
        while (mn < MAX && v2[mn] == 0) {
            mn++;
        }
        if (mx == 0 || mn == MAX) {
            break;
        }
        result = max(result, mx + mn);
        if (v1[mx] > v2[mn]) {
            v1[mx] -= v2[mn];
            v2[mn] = 0;
        }
        else {
            v2[mn] -= v1[mx];
            v1[mx] = 0;
        }
    }

    cout << result << "\n";
    }

}

 

 

---

 

 

 

백준 2036 : 수열의 점수

확실히 코드짜면서 테스트를 막 해봐야 하는데, 1이랑 0, 그리고 10, 11같은게 좀 섞여서 테스트를 해봐야한다.

문제에 함정이 있었는데, 1이 있는 경우에는 곱샘보단 덧셈이 이득이라 1은 더해야 하는 경우가 있었다.

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <fstream>
#include <stack>
#include <math.h>
#include <string>
#include <climits>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n = 0;
    cin >> n;

    vector<long long> VP;
    vector<long long> VM;

    for (long long i = 0; i < n; i++)
    {
        long long number = 0;
        cin >> number;

        if (number > 0)
        {
            VP.push_back(number);
        }
        else
        {
            VM.push_back(number);
        }
    }

    sort(VP.begin(), VP.end(), greater<long long>());
    sort(VM.begin(), VM.end(), less<long long>());

    long long ans = 0;
    for (int i = 0; i < VP.size(); i += 2)
    {
        if (i + 1 >= VP.size())
        {
            ans += VP[i];
            break;
        }
        else
        {
            if (VP[i] == 1 || VP[i + 1] == 1)
            {
                ans += VP[i];
                ans += VP[i + 1];
            }
            else
            {
                ans += (VP[i] * VP[i + 1]);
            }   
        }
    }
    for (int i = 0; i < VM.size(); i += 2)
    {
        if (i + 1 >= VM.size())
        {
            ans += VM[i];
            break;
        }
        else
        {
            ans += (VM[i] * VM[i + 1]);
        }
    }

    cout << ans;
}

 

 

---

 

 

 

백준 2785 : 체인

가장 작은 숫자를 기준으로 고리를 만들어준다고 계산했다.

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <fstream>
#include <stack>
#include <math.h>
#include <string>
#include <climits>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N = 0;
    cin >> N;

    vector<int> VN(N);
    for (int i = 0; i < N; i++)
    {   
        cin >> VN[i];
    }

    sort(VN.begin(), VN.end(), greater<int>());

    int Count = VN.size() - 1;
    int TargetN = VN.size() - 1;

    int answer = 0;
    while (true)
    {
        int Target = VN[TargetN];
        if (Target + 1 > Count)
        {
            answer += Count;
            break;
        }
        else
        {
            Count -= (Target + 1);
            answer += Target;
        }

        TargetN--;
    }

    cout << answer;
}

 

 

---

 

 

백준 2831 : 댄스파티

그냥 무난한 2포인터 문제. 근데 배열이 4개나 되어서 헷갈리긴했다.

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
#include <fstream>
#include <stack>
#include <math.h>
#include <string>
#include <climits>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N = 0;
    cin >> N;

    int answer = 0;

    int MP[1001] = {};
    int MM[1001] = {};
    int WP[1001] = {};
    int WM[1001] = {};

    for (int i = 0; i < N; i++)
    {
        int K = 0;
        cin >> K;
        if (K > 0)
        {
            MP[K - 1500]++;
        }
        else
        {
            MM[abs(K) - 1500]++;
        }
    }
    for (int i = 0; i < N; i++)
    {
        int K = 0;
        cin >> K;
        if (K > 0)
        {
            WP[K - 1500]++;
        }
        else
        {
            WM[abs(K) - 1500]++;
        }
    }

    int pp = 0;
    int mp = 0;
    while (pp <= 1000 && mp <= 1000)
    {
        while (pp <= 1000 && MP[pp] == 0) pp++;
        while (mp <= 1000 && WM[mp] == 0) mp++;

        while (pp <= 1000 && mp <= 1000)
        {
            if (pp < mp)
            {
                int pairs = min(MP[pp], WM[mp]);
                answer += pairs;
                MP[pp] -= pairs;
                WM[mp] -= pairs;
                break;
            }
            else
            {
                mp++;
            }
        }
    }

    pp = 0;
    mp = 0;
    while (pp <= 1000 && mp <= 1000)
    {
        while (pp <= 1000 && WP[pp] == 0) pp++;
        while (mp <= 1000 && MM[mp] == 0) mp++;

        while (pp <= 1000 && mp <= 1000)
        {
            if (pp < mp)
            {
                int pairs = min(WP[pp], MM[mp]);
                answer += pairs;
                WP[pp] -= pairs;
                MM[mp] -= pairs;
                break;
            }
            else
            {
                mp++;
            }
        }
    }
    cout << answer;
}