Problem Solving @ 2022/04/23

1. Barn Painting (G1) - From. USACO 2017 December Contest Gold 2번

 

 

시간 복잡도:

• O(N)

 

알고리즘:

• 트리 DP

 

말할 것 없는 간단한 트리 DP 문제입니다. DP 테이블을 다음과 같이 둡시다:

 

≫ dp[i][j] = i번째 노드를 j 색으로 칠할 때 경우의 수

 

이때, 현재 노드에 대해서 경우가 2가지 있고, 현재 노드에 연결된 노드에 대해 3가지 경우가 있습니다.

우선 현재 노드에 대한 경우를 봅시다.

 

• N-1. 이미 색이 안 칠해진 경우
• N-2. 이미 색이 칠해진 경우

 

그리고, 연결된 노드에 대한 경우를 봅시다.

 

• I-1. 이미 색이 안 칠해진 경우
• I-2. 이미 색이 칠해졌는데, 현재 노드와 색이 다른 경우
• I-3. 이미 색이 칠해졌는데, 현재 노드와 색이 같은 경우

 

N-2번과 I-2번은 dp 테이블을 먼저 0으로 맞추는 것으로 해결되고, I-3번의 경우가 있다면 그 즉시 0을 반환하는 것으로 해결됩니다. 이 외 경우는 현재 칠한 색과 다른 색으로 칠해주는 경우를 더하고, 그 결과값을 노드에 곱하면 됩니다.

 

#include <iostream>
#include <vector>

using namespace std;
#define MOD 1000000007
#define int long long

int N, K, precolor[100001];
vector<int> tree[100001];
int dp[100001][3];

int solve(int node, int color, int from) {

    if (tree[node].empty()) return 1;

    int& cache = dp[node][color];
    if (cache != -1) return cache;
    
    cache = 1;
    // pre-check 3
    for (int i = 0; i < tree[node].size(); i++) {
        int nxt = tree[node][i];
        if (nxt == from) continue;
        if (precolor[nxt] == color) return cache = 0;
    }

    // check 4, 2
    for (int i = 0; i < tree[node].size(); i++) {
        int nxt = tree[node][i];
        if (nxt == from) continue;

        int sum = 0;

        for (int j = 0; j < 3; j++) {
            if (color == j) continue;
            sum += solve(nxt, j, node);
        }

        cache = (cache * sum) % MOD;
    }

    return cache;
}

signed main() {

    cin >> N >> K;

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < 3; j++) {
            dp[i][j] = -1;
        }
        precolor[i] = -1;
    }

    for (int i = 0; i < N - 1; i++) {
        int from, to; cin >> from >> to;
        tree[from].push_back(to);
        tree[to].push_back(from);
    }

    for (int i = 0; i < K; i++) {
        int node, c; cin >> node >> c;
        c--; precolor[node] = c;
        for (int j = 0; j < 3; j++) {
            if (j == c) continue;
            dp[node][j] = 0;
        }
    }

    int ans = 0;
    for (int i = 0; i < 3; i++) {
        ans += solve(1, i, -1);
    }
    
    ans %= MOD;
    cout << ans << endl;
}

 

 

2. Haybale Feast (P5) - From. From. USACO 2017 December Contest Gold 3번

 

 

시간 복잡도:

• O(NlogN)

 

알고리즘:

• 세그먼트 트리
• 투 포인터

 

어려운 문제입니다. 여러 풀이 방법이 존재하고, 심지어 O(N) 풀이도 가능하지만, 저는 뇌가 딸려서 세그트리를 쓸 수밖에 없었습니다. (제일 쉬운 방법은 이분 탐색이라는 것이 정설입니다. 어떻게 하는지는 모르겠지만...)

 

두 개의 포인터를 각각 st, en 이라 하겠습니다.

이때, en을 넘지 않고 st~en의 맛의 합이 M이랑 최대한 가까워질 때까지 st를 늘려 나갑니다.

그 과정이 끝나고, st~en의 매운맛의 구간 최댓값을 세그먼트 트리를 이용해 구합니다.

마지막으로 en을 1 증가시켜줍니다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define int long long
#define MAX 8000000000000000003

int N, M;
int flavor[100001];
int spicy[100001];
int tree[100001 * 4];

void init(int node, int start, int end) {
    if (start == end) tree[node] = spicy[start];
    else {
        int mid = (start + end) / 2;
        init(node * 2, start, mid);
        init(node * 2 + 1, mid + 1, end);
        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }
}

int query(int node, int start, int end, int left, int right) {
    if (start > right || end < left) return 0;
    if (left <= start && end <= right) return tree[node];
    int mid = (start + end) / 2;
    int lmax = query(node * 2, start, mid, left, right);
    int rmax = query(node * 2 + 1, mid + 1, end, left, right);
    return max(lmax, rmax);
}

signed main() {


    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> flavor[i] >> spicy[i];
    }
    init(1, 1, N);

    int st = 1, en = 1;
    int sum = flavor[1];
    int ans = MAX;

    while (en <= N) {

        if (sum >= M) {
            while (true) {
                if (st == en || sum - flavor[st] < M) break;
                sum -= flavor[st]; st++;
            }

            ans = min(ans, query(1, 1, N, st, en));
        }
        en++; sum += flavor[en];
    }

    cout << ans << endl;

}