[중급 알고리즘] 그리디 (연습)

💚 1541 잃어버린 괄호

- 식에 괄호를 적절히 쳐서 식의 값을 최소로 만드는 문제

- -가 나오면 항상 뒤의 +(더하기) 식을 모두 묶으면 가장 큰 값을 뺀다.

- 어려운 부분: +와 숫자를 분리하는 부분

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    string s;
    cin >> s;
    vector<int> num;
    vector<int> sign;

    bool minus = false;
    int cur = 0;
    // 모든 숫자는 항상 양수이기 때문
    sign.push_back(1);

    // 문자열에서 숫자와 부호 분리
    for(auto c : s) {
        if(c == '+' || c == '-') {
            // +면 1, -면 -1
            if(c == '+') {
                sign.push_back(1);
            }
            else {
                sign.push_back(-1);
            }

            num.push_back(cur);
            cur = 0;
        }
        else {
            // 숫자인 경우 자릿수가 높은 숫자부터 인식하기 때문
            cur = cur * 10 + (c - '0');
        }
    }

    // 마지막 수도 배열에 넣기
    num.push_back(cur);

    // sign(첫번째는 + 고정) , num, sign, num, sign... 순으로 배열 확인
    // - 사이의 + 들을 모두 괄호치면 최소의 값 도출되기 때문
    int ans = 0;
    minus = false;
    for(int i = 0;i < num.size();i++) {
        if(sign[i] == -1) {
            minus = true;
        }
        if(minus) {
            ans -= num[i];
        }
        else {
            ans += num[i];
        }
    }

    cout << ans << '\n';
    return 0;
}

💚 1744 수 묶기

- 길이가 N인 수열에서 두 수를 적절히 묶어서 수열의 합을 최대로 하는 문제

- 수의 순서를 바꿔도 상관이 없다. ➡️ 그리디로 풀 수 있게 되는 조건! 큰 수부터 곱하자. 반대로 음수인 경우에는 작은 수끼리 곱하자(1은 제외)

- 같은 위치에 있는 수를 묶는 것은 불가능하고

- 각 수는 단 한 번만 묶거나 묶지 않아야 한다.

- 묶은 후에는 두 수의 곱이 수가 됨

- 이 때 최대 찾기

 

- 얌수는 큰수끼리

- 음수는 작은 수끼리

- 1은 묶지 않는 것이 최대

- 묶이지 않는 음수가 있는 경우 0을 이용할 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    vector<int> plus;
    vector<int> minus;
    cin >> n;
    int zero = 0;
    int one = 0;
    for(int i = 0;i < n;i++) {
        int x;
        cin >> x;
        if(x == 1) {
            one++;
        }
        else if(x > 0) {
            plus.push_back(x);
        }
        else if(x < 0) {
            minus.push_back(x);
        }
        else{
            zero++;
        }
    }

    sort(plus.begin(), plus.end());
    reverse(plus.begin(), plus.end());
    sort(minus.begin(), minus.end());
    // 양수의 개수가 홀수라면 1을 집어넣어서 짝수개로 맞춘 뒤
    // 모든 수를 둘씩 짝지어 곱셈 처리하는 내용으로 맞춰준다.
    if(plus.size() % 2 == 1) {
        plus.push_back(1);
    }

    // 음수의 개수가 홀수라면
    // 만약 0이 존재하면 0을 집어넣어서 가장 큰 음수를 무효화하고(왜냐면 가장 작은 음수는 그 다음 작은 음수와 곱하면 가장 큰 양수가 될 수 있기 때문
    // 만약 0이 존재하지 않는다면 임의로 1을 집어넣어서 곱셈 효과를 주되, 본연의 값이 그대로 나올 수 있도록 한다(a * 1 = a)
    if(minus.size() % 2 == 1) {
        minus.push_back(zero > 0 ? 0 : 1);
    }
    // 1은 곱셈보다 덧셈에 유리
    int ans = one;
    for(int i = 0; i < plus.size();i += 2) {
        ans += plus[i] * plus[i + 1];
    }

    for(int i = 0; i < minus.size();i += 2) {
        ans += minus[i] * minus[i + 1];
    }

    cout << ans << '\n';
}

💚 10610 30

- 어떤 수 N이 주어졌을 때, 숫자를 섞어 30의 배수로 만드는 문제

- 이 때 가장 큰 수를 만들어야 함

- N = 30, 답 = 30

- N = 102, 답 = 210

- N = 2931, 답 = 불가능

 

- 30은 3의 배수이자, 10의 배수이다.

- 자리의 합은 변하지 않기 때문에 마지막 자리만 0으로 만들어주면 된다.

- 가장 큰 수이기 때문에 그냥 내림차순 정렬을 하면 되는 문제

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    string s;
    cin >> s;
    int sum = 0;
    for(char c: s) {
        sum += c - '0';
    }

    sort(s.begin(), s.end());
    // 30의 배수인지 확인
    if(s[0] == '0' && sum % 3 == 0) {
        reverse(s.begin(), s.end());
        cout << s << '\n';
    }
    else {
        cout << "-1\n";
    }

    return 0;
}

💚 1783 병든 나이트

체스판의 크기가 매우 크기 때문에 모든 경우의 수를 해보는 것은 불가능하다.

이동 방향이 오른쪽이라는 점 사용

 

1. 높이가 1인 경우

움직일 수 없기 때문에 1

 

2. 높이가 2인 경우

두 가지 방법만 사용 가능하다. (+2, +1), (+2, -1)

따라서 정답은 min(4, (width + 1) / 2)

 

3. 높이가 3 이상인 경우

1) width >= 7

4가지 방법을 모두 1번씩 사용하면 (7, 1)으로 이동한다.

여기서부터 (+1, +2)와 (+1, -2)를 번갈아가면서 사용한다.

width - 2

 

2) width < 7

4가지 방법을 모두 사용할 수 없다.

(+1, +2)와 (+1, -2)를 번갈아가면서 사용할 수 있다.

min(4, width)

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int height, width;
    cin >> height >> width;
    // 무조건 우방향으로 가는 건 고정
    // 그래서 가로 길이로 조건절
    // 현재 최초의 자리만 가능
    if(height == 1) {
        cout << 1;
    }
    else if(height == 2) {
        // 위아래로 한 칸씩만 이동 가능한 경우만 가능
        cout << min(4, (width + 1) / 2);
    }
    else if(height >= 3) {
        // 4가지 경우 모두 한 번씩 수행 시 가로로 최소 7칸 필요
        if(width >= 7) {
            cout << width - 2;
        }
        else {
            cout << min(4, width);
        }
    }

    cout << '\n';
    return 0;

    return 0;
}

💚 12970 AB

- 정수 N과 K가 주어졌을 때, 다음 두 조건을 만족하는 문자열 S를 찾는 문제

- 0 <= i < j < N이면서 s[i] == 'A' && s[j] == 'B'를 만족하는 (i, j) 쌍이 0 ~ a * b가 되는 문자열을 항상 만들 수 잇다.

- A를 가장 앞에 추가하면 (i, j) 쌍이 b개 늘어나고, 가장 뒤에 추가하면 0개 늘어난다.

- 그래서 먼저 B를 b개 놓고, a를 어디에 추가하면 좋을지 선택한다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    for(int a = 0;a <= n;a++) {
        int b = n - a;
        // 최대 개수 : a * b
        if(a * b < k) continue;
        vector<int> cnt(b + 1);
        for(int i = 0;i < a;i++) {
            int x = min(b, k);
            // cnt[i]: A가 i번 위치에 몇 개?
            cnt[x] += 1;
            k -= x;
        }

        for(int i = b;i >= 0;i--) {
            for(int j = 0;j < cnt[i];j++) {
                cout << 'A';
            }
            if(i > 0) {
                cout << 'B';
            }
        }
        cout << '\n';
        return 0;
    }

    cout << -1 << '\n';
    return 0;
}

💚 12904 A와 B

- S를 T로 바꾸는 문제

- 가능한 연산

 

T의 마지막 문자가 A라면 A 연산을 사용해서 T를 만든 것

T의 마지막 문자가 B라면 B 연산을 사용해서 T를 만든 것

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    while(t.length() > s.length()) {
        if(t.back() == 'A') {
            t.pop_back();
        }
        else {
            t.pop_back();
            reverse(t.begin(), t.end());
        }
    }

    if(s == t) {
        cout << 1 << '\n';
    }
    else {
        cout << 0 << '\n';
    }
    return 0;
}