알고리즘 스터디 - 10주차

주식

문제 설명

홍준이는 다음과 같은 행동을 할 수 있다.
1. 주식 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.
날의 수와 각 날의 주가가 주어질 때, 최대 이익 구하라는 문제\

해결

1 ~ n일 중에서 최대를 가지는 주식을 고른다. 그러면 나는 그 전날까지의 주식을 다 사고,
그 날에 팔아버리는게 최대 이익이라는 점을 알 수 있다. 
그 때가 만약 5번째라고 했을 때, 나는 다시 6 ~ n일 중에서 최대를 가지는 주식을 고르고,
위와 같은 방법으로 진행하면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll a[1000001];
ll d[1000001];
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 s = 0;
        ll ans = 0;
        priority_queue<pair<ll, int>> q;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            q.push({a[i], i});
        }
        for (int i = 1; i <= n; i++) {
            d[i] = d[i - 1] + a[i];
        }
        while (!q.empty()) {
            ll z = q.top().first;
            int x = q.top().second;
            q.pop();
            if (x < s) continue;
            ans += z * (ll)(x - s) - (d[x] - d[s]);
            s = x;
        }
        cout << ans << '\n';
    }
}

회문

문제 설명

문자열이 주어지고, 해당 문자열이 팰린드롬이면 0을 출력,
해당 문자열 중에서 하나의 문자를 제거했을 때 팰린드롬이 되면 1을 출력, 
그렇지 않으면 2를 출력하는 문제

해결

단 한번만 제거를 할 수 있으므로, 먼저 앞과 끝에서부터 비교를 하면서 처음으로 어긋나는
지점을 구한다. 어긋나는 지점이 (x, y)라고 했을 때, 
1. (x + 1, y) -> x를 제거했을 경우 팰린드롬인지
2. (x, y - 1) -> y를 제거했을 경우 팰린드롬인지
를 비교해주고, 만약 팰린드롬이 아니면 2, 팰린드롬이면 1 어긋나는 지점이 없으면 0을 출력하도록 한다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int getDiffString(string s, bool f) {
    int l = 0;
    int r = (int)s.size() - 1;
    while (l < r) {
        if (s[l] != s[r]) {
            if (!f && (getDiffString(s.substr(l, r - l), 1) == 0 || getDiffString(s.substr(l + 1, r - l), 1) == 0)) {
                return 1;
            }
            return 2;
        }
        l += 1;
        r -= 1;
    }
    return 0;
}

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

    int testCase;
    cin >> testCase;
    while (testCase > 0) {
        string s;
        cin >> s;
        cout << getDiffString(s, 0) << '\n';
        testCase -= 1;
    }
}

뉴스 전하기

문제 설명

민식이의 회사는 트리 구조를 따르고, 민식이는 Root이다. 그리고 각 노드는 부모를 가지고 있다.
각 직원은 각 부하들에게 전화를 해 뉴스를 전달하는데 1분이 걸린다.
모든 직원이 뉴스를 듣는데 걸리는 최소시간을 구하는 문제

해결

d[x] = x번째 사람이 부하들에게 연락을 돌리는데 걸리는 최소 시간
리프노드는 부하들이 없으므로 d[leafNode] = 0이 된다.
그리고 현재 x노드에 있다고 가정할 때, 나는 어떤 부하들에게 전화를 먼저 돌려야 할까?
그리디스럽게 접근해보면 부하들 중에서 가장 시간이 오래걸리는 부하들에게 먼저 전화를
돌리는게 이득이라는 점을 알 수 있다.
리프노트부터 시작해서 루트까지 올라가면서 해당 부하들 중에서 가장 시간이 오래 걸리는 
부하들에게 먼저 전화를 거는 방식으로 코드를 짜면 해결할 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
vector<int> a[51];

int go(int x) {
    // 리프토드면 0을 반환
    if (a[x].empty()) return 0;
    vector<int> v;
    // 부하들의 걸리는 시간을 계산 + 1(내가 전화를 거는 시간)
    for (int next : a[x]) {
        int x = go(next) + 1;
        v.push_back(x);
    }
    // 부하들의 걸리는 시간이 큰 순으로 정렬
    sort(v.rbegin(), v.rend());
    int ans = 0;
    // 부하들이 걸리는 시간 + 내가 전화를 거는 시간중 최댓값을 구한다.
    for (int i = 0; i < (int)v.size(); i++) {
        ans = max(ans, v[i] + i);
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        x += 1;
        if (x == 0) continue;
        a[x].push_back(i);
    }

    cout << go(1) << '\n';
}