알고리즘 스터디 - 7주차

체인

문제 설명

N개의 체인이 있고, 체인은 고리로 이루어져 있다. 
이 체인을 하나의 체인으로 만들기 위해 열고 닫아야하는 최소한의 고리 수를 구하는 문제

해결

하나의 고리는 무조건 2개의 체인을 연결할 수 있다. 따라서 제일 작은 체인부터 시작하여 고리를
하나씩 제거하면서 각 체인들을 연결시켜주면서 체인이 1개가 되는 경우를 구하면 된다. 

OO OOO OOOO OOOOO 의 4개의 체인이 있다고 가정하자.
우리는 제일 작은 체인부터 고리를 쓰면 체인을 연결시킬 수 있는 개수가 줄어들기 때문에 최적임을
직감으로 알 수 있다. 
따라서 2개의 고리로 이루어진 체인을 1개씩 써보는 방식을 생각할 수 있다.
(아무리 많아도 전체 체인은 N - 1개로 구성가능함)
1개를 썼을 때 남아 있는 체인은 4개고, 이 4개의 체인은 최소 3개의 체인이 필요하다. 따라서 
1개로는 불가능임을 알 수있고, 다음으로 넘어가는 방식으로 코드를 작성하면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int a[500001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);

    int j = 0;
    for (int i = 1; i < n; i++) {
        a[j] -= 1;
        if (a[j] == 0) j += 1;
        if (n - j - 1 <= i) {
            cout << i << '\n';
            return 0;
        }
    }
}

수열의 점수

문제 설명

N개의 정수가 있고, 한 정수를 제거할 때는 그 정수가 점수가 되고, 두 정수를 제거할 때는
곱이 점수가 된다. 전부 제거했을 때 얻을 수 있는 점수의 최댓값

해설

양수, 음수(0 포함)를 따로 구해놓고, 제일 큰 값, 2번째로 큰 값을 곱해주면서 마지막 1개가
남으면 그 수를 더해주는 방식으로 진행한다. 
예외(1, 2인 경우는 더하는게 이득)만 처리해주면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

    ll ans = 0;
    int n;
    cin >> n;
    vector<ll> mv, pv;
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        if (x <= 0)
            mv.push_back(-x);
        else
            pv.push_back(x);
    }
    sort(mv.rbegin(), mv.rend());
    sort(pv.rbegin(), pv.rend());

    for (int i = 0; i < pv.size(); i++) {
        if (i + 1 < pv.size()) {
            ans += max(pv[i] + pv[i + 1], pv[i] * pv[i + 1]);
            i += 1;
        } else {
            ans += pv[i];
        }
    }

    for (int i = 0; i < mv.size(); i++) {
        if (i + 1 < mv.size()) {
            ans += mv[i] * mv[i + 1];
            i += 1;
        } else {
            ans -= mv[i];
        }
    }

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

스타트 택시

문제 설명

N X N 크기의 격자에서 M명의 승객을 태워 목적지까지 이동해야하는 것이 목표이다.
M명의 승객은 각자의 현재 위치, 목적지가 주어지고 아래와 같은 규칙을 지켜야 한다.
1. 현재 위치에서 가장 가까운 승객을 먼저 태운다.
2. 손님을 성공적으로 목적지로 이동시키면 그 승객을 태워 이동하면서 걸린 연로 * 2를 더한다.
3. 모든 손님을 태울 수 없으면 -1을 출력한다.
4. 모든 손님을 태울 수 있으면 마지막에 남은 연료의 양을 출력

해설

코딩테스트 문제는 단순히 지문을 알기쉽게 해석하는게 중요한 것 같다. 
문제에 나와 있는 규칙을 지키면서 구현을 진행하면 된다. 
신경 써야할 점
1. 해당 위치에서 손님 위치로 갈 때 연료가 충분한가? 또는 갈 수 있는가?
2. 손님 위치에서 목적지까지로 갈 때 연료가 충분한가? 또는 갈 수 있는가?

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int n, m, k;
struct A {
    int x, y, nx, ny;
    bool operator<(const A obj) {
        if (x == obj.x) return y < obj.y;
        return x < obj.x;
    }
} b[401];
bool check[401];
int a[21][21];
int d[21][21];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void go(int s, int e) {
    queue<pair<int, int>> q;
    memset(d, -1, sizeof(d));
    q.push({s, e});
    d[s][e] = 0;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 1 || ny < 1 || nx > n || ny > n || a[nx][ny] == 1 || d[nx][ny] != -1) continue;
            d[nx][ny] = d[x][y] + 1;
            q.push({nx, ny});
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    int s, e;
    cin >> s >> e;

    for (int i = 0; i < m; i++) {
        cin >> b[i].x >> b[i].y >> b[i].nx >> b[i].ny;
    }
    sort(b, b + m);
    for (int t = 0; t < m; t++) {
        int cnt = 0, idx = -1;
        go(s, e);
        for (int i = 0; i < m; i++) {
            if (check[i] || d[b[i].x][b[i].y] == -1) continue;
            if (idx == -1 || cnt > d[b[i].x][b[i].y]) {
                cnt = d[b[i].x][b[i].y];
                idx = i;
            }
        }
        if (idx == -1) {
            cout << -1 << '\n';
            return 0;
        }
        go(b[idx].x, b[idx].y);
        s = b[idx].nx, e = b[idx].ny;
        if (d[s][e] == -1 || k - cnt - d[s][e] < 0) {
            cout << -1 << '\n';
            return 0;
        }
        check[idx] = true;
        k += (d[s][e] - cnt);
    }
    cout << k << '\n';
}

⚾

문제 설명

9명이 야구를 진행하는데, 총 N이닝을 진행하면서 가장 많이 득점을 할 수 있는 타순을 찾는 문제
(1번은 고정으로 4번)
규칙은 야구의 규칙과 동일하다. 

해설

여러방식으로 해결할 수 있지만, 나는 비트마스킹을 사용했다. 현재 그라운드를 x = 0이라는 변수에
두고 아래와 같은 결과가 나올 때 알맞게 처리하면 된다.
x = 000을 각각 왼쪽부터 3루, 2루, 1루로 가정하고 진행하고 함수가 필요하다.

1. getPoint() -> 점수를 냈을 경우 몇점을 얻었는지 알 수 있는 함수
점수를 얻었다는 거는 4번째비트, 5번째비트, 6번째비트들 중에 1이 있다는 것을 의미하므로 해당 
비트들을 비교해주는 로직과, 0으로 처리해주는 로직을 함께 작성

1. 1루타 -> x *= 2, ans += getPoint(x), x += 1
2. 2루타 -> x *= 4, ans += getPoint(x), x += 2
3. 3루타 -> x *= 8, ans += getPoint(x), x += 4
4. 홈런 ->  x *= 8, ans += getPoint(x) + 1

이를 전체 경우를 비교해주면서 할 수 있다.
시간복잡도를 계산하는게 꽤 애먹었는데, 내 생각에는
O(9! + 8! * 27 * n) 인거 같다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int a[51][11];
int n;

int getPoint(int &x) {
    int cnt = 0;
    for (int i = 3; i < 6; i++) {
        if (x & (1 << i)) {
            cnt += 1;
            x -= (1 << i);
        }
    }
    return cnt;
}
int go(vector<int> &v) {
    int ans = 0;
    int s = 0;
    for (int i = 0; i < n; i++) {
        int so = 0, x = 0;
        while (so < 3) {
            if (a[i][v[s]] == 1) {
                x *= 2;
                ans += getPoint(x);
                x += 1;
            } else if (a[i][v[s]] == 2) {
                x *= 4;
                ans += getPoint(x);
                x += 2;
            } else if (a[i][v[s]] == 3) {
                x *= 8;
                ans += getPoint(x);
                x += 4;
            } else if (a[i][v[s]] == 4) {
                x *= 8;
                ans += getPoint(x) + 1;
            } else {
                so += 1;
            }
            s += 1;
            s %= 9;
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<int> v;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 0; i < 9; i++) {
        v.push_back(i);
    }

    int ans = 0;

    do {
        if (v[3] != 0) continue;
        ans = max(ans, go(v));
    } while (next_permutation(v.begin(), v.end()));
    cout << ans << '\n';
}