Good Bye 2021: 2022 is NEAR A부터 C까지 업솔빙

Good Bye 2021: 2022 is NEAR A부터 C까지 업솔빙

B번까지 풀었는데, 퍼포먼스가 1300까지 나오는 기적? B번을 생각보다 빨리 풀어서 그런것 같다. 나는 쉬운 문제 셋보다 어려운 문제셋에 더 강점이 있는 것 같다는 생각을 요즘 계속 하는 중이다. 쉬운 문제셋은 생각보다 당황을 많이 하는데, 어려운 문제셋은 최선을 다해서 풀려고 해서 그런것 같다. 이번에는 C번까지 업솔빙을 해봤으니 공부가 더 많이 된것 같다.

A. Integer Diversity (*800)

접기/펼치기

문제 설명
$n$개 정수 $a_1,a_2,...,a_n$이 주어진다. 주어진 숫자의 아무 부분 집합을 선택해서 이 숫자들의 부호를 바꾼다. 이때 이 연산은 횟수 제한이 없다.
우리가 얻을 수 있는 배열 중에서 서로 다른 숫자의 최대 개수는 몇개일까?

문제 해설
같은 숫자가 2개 이상 있으면 음수와 양수, 총 2개까지만 서로 다른 숫자가 만들어진다. 그렇기 때문에 map을 사용하던, 크기가 101인 배열을 사용하던 해서 개수가 1개이면 1을 더하고, 2개 이상이면 2를 더하면 답이 나온다.

이때 주어진 숫자에 절댓값을 씌워서 확인을 해야하는 것을 잊지 말아야 한다. 그리고 0인 경우는 음수와 양수 구분이 없기 때문에 1개 이상이면 1을 더해야 하는 것도 주의해야 할 점이다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int cnt[101] = {0, };
        for(int i = 0; i < n; i++){
            int num; cin >> num;
            cnt[abs(num)]++;
        }

        int ans = 0;
        for(int i = 1; i <= 100; i++){
            ans += (cnt[i] > 0 ? (cnt[i] > 1 ? 2 : 1) : 0);
        }
        cout << ans + (cnt[0] > 0) << "\n";
    }
    return 0;
}

B. Mirror in the String (*1100)

접기/펼치기

문제 설명
길이가 $n$인 문자열 $s$가 있다. 문자열을 왼쪽부터 오른쪽으로 살펴보는데, index $k(1\le k\le n)$를 선택하고 $k$번째 단어 이후에 거울을 둔다. 그러면 다음 문자열이 만들어진다. $s_1{s}_2...s_k{s}_k{s}_{k-1}...s_1$ 우리가 만들 수 있는 문자열 중, 사전순으로 가장 작은 문자열은 무엇일까?

문제 해설
이것도 한가지 주의할 점만 빼면 쉽게 풀 수 있었던 문제다. 결국 왼쪽부터 차례대로 그리디하게 보다가 다음 문자가 현재 문자보다 커지면 현재 문자 뒤에다 거울을 두면 된다. 왜 그렇게 되는지는 직접 구성해보면 쉽게 규칙을 찾을 수 있다.

이때 한가지 주의해야할 점은 맨 앞 두 문자가 같으면 무조건 가장 작은 문자열은 두 문자를 연속으로 쓰는 것이기 때문에 예외처리를 해줘야 한다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        string s; cin >> s;
        if(s[0] == s[1]){
            cout << s[0] << s[1] << "\n";
            continue;
        }
        int k = n - 1;
        for(int i = 0; i < n - 1; i++){
            if(s[i] < s[i + 1]){
                k = i;
                break;
            }
        }

        for(int i = 0; i <= k; i++) cout << s[i];
        for(int i = k; i >= 0; i--) cout << s[i];
        cout << "\n";
    }
    return 0;
}

C. Representative Edges (*1500)

접기/펼치기

문제 설명
배열 $a_1,a_2,...,a_n$은 다음 조건을 만족하면 좋은 수열이라고 정의한다.

• 모든 $l,r$에 대해서 $1\le l\le r\le n$ , 다음 식을 만족해야 한다. $a_l+a_{l+1}+...+a_r=\frac{1}{2}(a_l+a_r)\cdot (r-l+1)$

주어진 배열 $a_1,a_2,...,a_n$에 대해서, 한번의 연산은 이 배열중 한개의 원소를 아무 실수로 바꿀 수 있다. 이 배열을 좋은 수열로 만들기 위해서 필요한 최소 연산 횟수를 구하라.

문제 해설
일단 문제에 나온 식의 의미를 알아야한다. 자세한것은 구글에 물어보고, 저 식은 바로 $a_l$부터 $a_r$까지 등차수열을 이뤄야 한다는 것과 같다. 그런데 모든 $l,r$에 대해서 저 식을 만족해야 하기 때문에 즉 전체 배열의 원소가 서로 등차수열을 이뤄야 한다는 뜻과 동치이다.

일단 최악의 경우는 몇번의 연산이 필요할까? 그냥 수 하나를 정하고 나머지 $n-1$개 수를 임의로 등차수열로 만들면 된다. 즉 $n-1$번 연산이 필요하다.
그런데 이 배열 원소의 최대 개수가 $70$개 이므로 그냥 완전탐색을 하면 풀린다. 이중 for문을 사용해서 $l$과 $r$의 index를 고정하고, $k$를 $1$부터 $n$까지 순회하면서 등차수열 조건을 만족 못시키는 원소의 개수를 구한다. 그리고 그 개수의 최솟값을 구하면 된다.

그러면 등차수열 조건은 어떻게 쉽게 구성할 수 있을까? 등차수열의 일반항 공식을 사용하면 된다.
맨 왼쪽 index를 $l$, 맨 오른쪽 index를 $r$, 가운데 index를 $k$라고 하면 다음 식을 만족한다.
$a_l+d\times (k-l)=a_k$ 이때 공차 $d$는 다음과 같다. $d=\frac{a_r-a_l}{r-l}$ 이기 때문에 두 식을 정리하면 $(a_r-a_l)\times (k-l)=(a_k-a_l)\times (r-l)$이 된다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int a[n];
        for(auto& x : a) cin >> x;

        int ans = n - 1;
        for(int i = 0; i < n - 1; i++){
            for(int j = i + 1; j < n; j++){
                int cnt = 0;
                for(int k = 0; k < n; k++){
                    if((a[j] - a[i]) * (k - i) != (a[k] - a[i]) * (j - i)) cnt++;
                }
                ans = min(ans, cnt);
            }
        }
        cout << ans << "\n";
    }
    return 0;
}