Codeforces Round #759 (Div. 2, based on Technocup 2022 Elimination Round 3) 1496 -> 1486

Dashboard - Codeforces Round #759 (Div. 2, based on Technocup 2022 Elimination Round 3) - Codeforces

Dashboard - Codeforces Round #759 (Div. 2, based on Technocup 2022 Elimination Round 3) - Codeforces

 !!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!

 

 

A. Life of a Flower

Problem - A - Codeforces

Problem - A - Codeforces

문제

 

꽃에 물을 줘야한다. 2일동안 물을 못주면 꽃은 죽고, 하루동안 물을주면 1센티가 자라는데, 전날에도 물을주면 5센티가 자란다. 꽃에 물을 준 날을 기록했을 때 꽃의 키를 구하는 문제

 

풀이

 

그대로 구현한다

 

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int a[101];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int ans = 1;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= n; i++) {
            if (a[i]) {
                ans++;
                if (a[i - 1])ans += 4;
            }
            else {
                if (i == 1)continue;
                if (a[i - 1] == 0) {
                    ans = -1;
                    break;
                }
            }
        }
        cout << ans << '\n';
    }
}

 

 

B.  Array Eversion

Problem - B - Codeforces

Problem - B - Codeforces

 

문제

 

길이가 n인 배열 a가 주어진다. 각 배열에서 가장 오른쪽 숫자 기준으로 작은 것은 왼쪽, 큰것은 오른쪽으로 Replace 하는 작업이 주어질 때 배열이 바뀌지 않는 최소 연산 횟수 k를 출력하는 문제

 

풀이

 

오른쪽 끝에서부터 MAX값을 갱신할 때마다 카운트를 증가시켜주고 카운트 값을 출력한다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int a[200001];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)cin >> a[i];
        int ans = -1, MAX = 0;
        for (int i = n; i > 0; i--) {
            if (MAX < a[i]) {
                ans++;
                MAX = a[i];
            }
        }
        cout << ans << '\n';
    }
}

C.  Minimize Distance

Problem - C - Codeforces

Problem - C - Codeforces

 

문제

 

n개의 장소에 가방을 놔두려고 한다. 0지점에 모든 가방이 있고 한번에 k개의 가방을 들고 이동할 수 있다. 이때 모든 장소에 가방을 놔두기 위해 움직여야할 최소 거리의 수를 출력하는 문제

 

풀이

 

양수구간 음수구간을 따로 나누고, 가장 큰 구간을 마지막으로 방문한다. 각 구간별로 마지막부터 k개를 탐색하는 것이 최소거리가 된다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
long long a[200001];
vector<long long> v1, v2;
long long ans = 0;
int n, k;
//0은 끝찍고 돌아오는거
//1은 마무리
void go1(int type) {
    int size1 = v1.size();
    size1 -= k;
    for (int i = size1-1; i >=0; i -= k) {
        ans += v1[i] * 2LL;
    }
    if (type)ans += v1.back();
    else ans += v1.back() * 2LL;
}
void go2(int type) {
    int size2 = v2.size();
    size2 -= k;
    for (int i = size2-1; i >=0; i -= k) {
        ans += v2[i] * 2LL;
    }
    if (type)ans += v2.back();
    else ans += v2.back() * 2LL;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> k;
        v1.clear(); v2.clear();
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] > 0)v1.push_back(a[i]);
            else if(a[i]<0)v2.push_back(-a[i]);
        }
        ans = 0;
        if (v1.empty() && v2.empty()) {
            cout << 0 << '\n';
            continue;
        }
        sort(v1.begin(), v1.end());
        sort(v2.begin(), v2.end());
        if (v1.empty()) {
            go2(1);
            cout << ans << '\n';
            continue;
        }
        if (v2.empty()) {
            go1(1);
            cout << ans << '\n';
            continue;
        }
        if (v1.back() >= v2.back()) {
            go2(0);
            go1(1);
        }
        else {
            go1(0);
            go2(1);
        }
        cout << ans << '\n';
    }
}

 

 

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.