[중급 알고리즘] 그리디(도전)

💚 1201 NMK

- 가장 긴 증가하는 부분 수열의 문제는 대부분 다이나믹 프로그래밍이나 그리디의 형식으로 문제를 푼다.

- 적어도 M개의 정수는 증가 수열에 포함되어야 하고

- 적어도 K개의 정수는 감소 수열에 포함되어야 한다.

- 두 수열은 최대 정수 1개를 공유할 수 있기 때문에 

- N >= M + k + 1이어야 한다.

 

- 또 N은 MK를 넘을 수 없다.

- N = MK + 1인 경우에 길이가 M + 1인 증가 수열이나 길이가 K + 1인 감소 수열을 반드시 만들 수 있따.

- 비둘기집 원리로 증명할 수 있음

- Erdos-Szekeres Theorem

 

증가하는 수열을 뒤집으면 반드시 감소하는 수열이 된다.

ex) 3478 ➡️  8743

 

M + K - 1 <= N <= MK인 경우에만 답을 찾을 수 있다.

 

ex)

1,2,3,4,5,6,7,8,9

 

뒤의 나머지 K개의 수를 뒤집는다.

1,2,3,4,   9,8,7,6,5

 

모든 증가하는 부분 수열을 뒤집은 후 각 그룹에서 하나씩만 선택하면 가장 긴 증가수열이 될 수 있다.

이 성질을 이용해서 문제를 풀 수 있다.

그룹의 크기 = 감소하는 부분 수열의 길이

그룹의 개수 = 증가하는 부분 수열의 길이

 

1. 1부터 N까지 수를 오름차순으로 적는다.

2. 수를 M등분한다. 이 때 그룹에 들어있는 수는 K보다 작거나 같아야 하며, 적어도 한 그룹은 들어있는 수의 개수가 K이어야 한다.

3. 각 그룹에 들어있는 수의 순서를 뒤집는다.

 

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

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    // 그룹의 크기 = 감소하는 부분 수열의 길이
    // 그룹의 개수 = 증가하는 부분 수열의 최대 길이
    if(m + k - 1 <= n && n <= m * k) {
        for(int i = 0;i < n;i++) {
            a[i] = i + 1;
        }
        // 그룹의 경계 저장
        vector<int> g;
        g.push_back(0);
        // 최대 길이의 그룹을 우선 전제하고 시작
        g.push_back(k);
        n -= k;
        m -= 1;

        // gs: m개의 그룹을 만들기 위해 필요한 그룹의 길이
        int gs = m == 0 ? 1 : n / m;
        // m개의 그룹을 만들고 남은 수
        int r = m == 0 ? 0 : n % m;

        for(int i = 0;i < m;i++) {
            // 이전 그룹의 경계 + 그룹의 길이
            // k보다 길어지는 경우는 불가능
            g.push_back(g.back() + gs + (r > 0 ? 1 : 0));
            if(r > 0) {
                r -= 1;
            }
        }

        for(int i = 0;i < g.size() - 1;i++) {
            reverse(a.begin() + g[i], a.begin() + g[i + 1]);
        }

        for(int i = 0;i < a.size();i++) {
            cout << a[i] << ' ';
        }

        cout << '\n';
    }
    else {
        cout << "-1\n";
    }
    return 0;
}

💚 2873 롤러코스터

방문한 칸의 숫자의 합을 최대로 해야하기 때문에 모든 칸을 방문하는 것을 지향한다.

width, height의 홀수, 짝수에 따라 모든 칸을 방문할 수 있는지에 따라 다르다.

 

증명

- 모든 칸을 체스판 처럼 검정과 흰색으로 칠했다고 치자

- (1, 1)과 (R,C)의 색은 흰색이다.

- (1, 1)과 (R,C)로 가는 모든 경로는 흰 ➡️ 검 ➡️ 흰 ➡️ 검...

- 방문한 칸은 흰 > 검이다.

- 방문하지 않은 칸 흰 < 검이다.

- 따라서 모든 칸을 방문하는 것이 불가능

 

짝 * 짝 = 짝수 ➡️ 흰색의 개수 = 검은색의 개수

 

따라서 R 또는 C가 홀수면 모든 칸을 방문할 수 있고, R과 C가 모두 짝수면 모든 칸을 방문하는 것은 불가능

흰 칸 한 칸을 방문하지 않는다면 나머지 칸은 모두 방문 불가

검정 한 칸을 방문하지 않는다면 나머지 칸은 모두 방문 가능

 

따라서 방문히지 않을 검정 칸 하나를 선택해야 함

방문한 칸의 합의 최대를 구하는 문제이기 때문에 가장 작은 검은색 칸을 선택!

 

보통의 경로 찾기 문제의 경우, A를 이동시키고 B는 고정시키지만 이 문제에서는 체스판 위에 A와 B를 같이 이동시킨다.

#include <iostream>
#include <algorithm>
using namespace std;
int a[1000][1000];

void append(string &s, char c,int cnt) {
    for(int i = 0; i < cnt;i++) {
        s += c;
    }
}
int main() {
    // 행, 열
    int n, m;
    cin >> n >> m;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            cin >> a[i][j];
        }
    }

    string s = "";
    // 행이 홀수이면 ㄹ자를 그리면서 도착점에 도착
    if(n % 2 == 1) {
        for(int i = 0;i < n;i++) {
            if(i % 2 == 0) {
                append(s, 'R', m -1);
                // 마지막 줄이 아닌 이상 아래 줄로 내려가는 모션도 추가
                if(i != n - 1) {
                    append(s, 'D', 1);
                }
            }
            else {
                append(s, 'L', m - 1);
                append(s, 'D', 1);
            }
        }
    }
    else if(m % 2 == 1){
        // 행은 짝수, 열은 홀수
        // ㄹ자를 오른쪽으로 90도 회전하여 진행, 즉 위 내용을 행과 열만 바꿔서 진행
        for(int i = 0;i < m;i++){
            if(i % 2 == 0) {
                append(s, 'D', n - 1);
                if(i != m - 1) {
                    append(s, 'R', 1);
                }
            }
            else {
                append(s, 'U', n - 1);
                append(s, 'R', 1);
            }
        }
    }
    else {
        // 행과 열이 모두 짝수
        int x, y;
        // 초기화
        x = 0;
        y = 1;
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                // 검정 칸 중에서
                if((i + j) % 2 == 1) {
                    // 가장 값이 작은 칸 위치 구하기
                    if(a[x][y] > a[i][j]) {
                        x = i;
                        y = j;
                    }
                }
            }
        }


        // A(출발점)
        int x1 = 0;
        int y1 = 0;
        // B(도착점)
        int x2 = n - 1;
        int y2 = m - 1;

        string s2 = "";
        // 마지막에는 항상 2 * 2 칸만 남기 때문
        // 1번
        // A O
        // X(최소값의 검은 칸) B
        // 2번
        // A X(최소값의 검은 칸)
        // O B
        // 우선 행부터 이동하고 다음에 열 이동
        while(x2 - x1 > 1) {
            // 2행씩 이동하기 때문
            if(x1 / 2 < x / 2) {
                append(s, 'R', m - 1);
                append(s, 'D', 1);
                append(s, 'L', m - 1);
                append(s, 'D', 1);
                x1 += 2;
            }

            if(x / 2 < x2 / 2) {
                append(s2, 'R', m - 1);
                append(s2, 'D', 1);
                append(s2, 'L', m - 1);
                append(s2, 'D', 1);
                x2 -= 2;
            }
        }

        while(y2 - y1 > 1) {
            if(y1 / 2 < y / 2) {
                append(s, 'D', 1);
                append(s, 'R', 1);
                append(s, 'U', 1);
                append(s,'R', 1);
                y1 += 2;
            }

            if(y / 2 < y2 / 2) {
                append(s2, 'D', 1);
                append(s2, 'R', 1);
                append(s2, 'U', 1);
                append(s2,'R', 1);
                y2 -= 2;
            }
        }

        if(y == y1) {
            append(s, 'R', 1);
            append(s, 'D', 1);
        }
        else {
            append(s, 'D', 1);
            append(s, 'R', 1);
        }

        reverse(s2.begin(), s2.end());
        s += s2;
    }

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

💚 12919 A와 B 2

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

- T의 첫 문자가 B라면, B연산을 사용해서 T를 만든 것이다.

 

위 설명을 이용하여

경우의 수를 총 4가지로 만든 것이다.

A...A(A연산)

A...B(불가능)

B...A(문제 발생, A연산도 가능 B연산도 가능하기 때문에 모두 조사하면 된다.)

B...B(B연산)

 

두 방법으로 나누어지는 경우가 총 N - 1번 있다.

모든 단계에서 문자열의 길이가 1씩 감소하기 때문에 총 가능한 (S, T)의 조합은 N^2개 있다.

문자열의 연산은 O(N)이기 때문에 시간 복잡도는 O(N^3)이다. 

 

#include <iostream>
#include <algorithm>

using namespace std;

string cut(string s) {
    s.pop_back();
    return s;
}

string rev(string s) {
    reverse(s.begin(), s.end());
    return s;
}

bool can(string s, string t) {
    if(s == t) return true;
    if(t.length() > 0) {
        // 재귀
        if(t.back() == 'A' && can(s, cut(t))) {
            return true;
        }
        if(t[0] == 'B' && can(s, cut(rev(t)))) {
            return true;
        }
    }

    return false;
}

int main() {
    string s, t;
    cin >> s >> t;
    cout << can(s, t) << '\n';
    return 0;
}