P2 1814 지붕 색칠하기

1시간 2분 32초
마을의 지도를 1번 집이 root가 되도록 트리로 그렸다.
이떄 각 집마다 가장 적은 비용을 들게 하는 색 c1과 두 번째로 적은 비용을 들게 하는 색 c2를 저장하도록 한다.
만약 부모 집의 색과 현재 집의 c1이 다르다면 그냥 c1을 칠하면 되고,
부모 집의 색과 현재 집의 c1이 같다면 현재 집에는 c2를 칠하면 된다.

코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define f first
#define s second
#define all(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

const int MXN = 1e4 + 1;
int N, M;
vector<int> g[MXN];
int colorPrice[MXN];
int parent[MXN];

// pair< pii(첫번째 색, 첫번쨰 점수), pii(두번째 색, 두번쨰 점수) >
vector<tuple<bool, pii, pii>> cost(MXN);

void makeTree(int here) {
    for(int there : g[here]) {
        if(there == parent[here]) continue;
        parent[there] = here;
        makeTree(there);
    }
}

int paint(int usedColor, int here) {
    bool &already = get<0>(cost[here]);
    pii &first = get<1>(cost[here]);
    pii &second = get<2>(cost[here]);

    if(already) {
        if(first.f != usedColor) return first.s;
        return second.s;
    }

    int ret = INF;
    for(int color = 1; color <= M; color++) {
        int res = colorPrice[color];
        for(int there : g[here]) {
            if(there == parent[here]) continue;
            res += paint(color, there);
        }
        if(color != usedColor) ret = min(ret, res);

        if(res < first.s) {
            second = first;
            first.f = color, first.s = res;
        }
        else if(res < second.s) {
            second.f = color, second.s = res;
        }
    }
    already = true;
    return ret;
}

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

    cin >> N;
    for(int i=0; i<N-1; i++) {
        int a,b; cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    cin >> M;
    for(int i=1; i<=M; i++) {
        cin >> colorPrice[i];
    }

    // make tree by root 1
    makeTree(1);

    // init cost
    for(int i=1; i<=N; i++) {
        cost[i] = make_tuple(false, pii(0,INF), pii(0,INF));
    }

    // paint tree started by root 1
    cout << paint(0,1) << '\n';

    return 0;
}

코드 설명

구현은 대체로 무난한데 paint 함수는 구현에 신경써야 하는 부분이 있었다.

• int paint(int usedColor, int here)
  paint 함수는 현재 집에 색을 다 칠해보고 가장 적은 비용을 반환하는 함수다.
  그 과정에서 (비용이 적은 순으로) 첫번째 색과 점수, 그리고 두번째 색과 점수를 cost 배열에 저장한다.
  이때의 cost 배열은 부모 집 색 usedColor를 포함해서 계산해야 하지만 paint 함수의 리턴 값인 ret는 usedColor의 경우는 포함시키지 않는 것이 중요하다.
  모든 색을 확인해서 cost 배열을 완전히 업데이트 시킨 경우 다시 계산하지 않고 배열을 반환할 수 있도록 already 불리언 값을 저장해준다.

후기

처음에는 단순하게 dp[부모 집 색][현재 집 번호]를 생각했지만, (400mb으로) 메모리 부족을 예상할 수 있다.
이때 시간은 얼추 괜찮지만(10^8 정도) 메모리는 부족하다는 것으로부터 생각을 확장시켜 나갔다.
트리 구조에서 부모->자식 방향으로 내려간다고 생각했을 때 부모 집 색만 신경쓰면 된다.
그럼 (현재 노드를 subtree의 root라 할 때) subtree의 비용이 가장 적도록 하는 색 2개만 알고 있으면 해결되겠다는 생각을 했고 그 나머지는 구현만 하면 되는 문제였다.

P3 Huge Integer!

2시간 50분 38초
거듭제곱 알고리즘을 바로 떠올렸으나 $O(Nlog_2(B)) = C\times10^8$ 이지만 $C$ 값이 큰 지 부분 점수만 받을 수 있었다. 이를 최적화시키기 위해 다음과 같은 배열에 값을 저장해서 이용했다.

ll powBy10[MXN]; // powBy10[x] = 10^(2^x)
ll ones[MXN]; // ones[x] = (11...1) % K, (11...1)'s count = 2^x

B의 최댓값이 $10^{18}$이기 때문에 $log_2{(10^{18}}) = 59.794...$이라서 MXN = 60으로 설정했다.

코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define f first
#define s second
#define all(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
using pll = pair<ll, ll>;

const int MXN = 60;
ll N, K;
vector<pll> v;
ll powBy10[MXN]; // powBy10[x] = 10^(2^x)
ll ones[MXN]; // ones[x] = (11...1) % K, (11...1)'s count = 2^x

void init_powBy10() {
    powBy10[0] = 10%K;
    for(int cnt=1; cnt<MXN; cnt++) {
        powBy10[cnt] = (powBy10[cnt-1] * powBy10[cnt-1]) % K;
    }
}
void init_ones() {
    ones[0] = 1;
    for(int cnt=1; cnt<MXN; cnt++) {
        ones[cnt] = (ones[cnt-1]*powBy10[cnt-1] + ones[cnt-1]) % K;
    }
}

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

    cin >> N >> K;
    v.resize(N);
    for(int i=0; i<N; i++) {
        cin >> v[i].f >> v[i].s;
    }

    init_powBy10();
    init_ones();

    ll ans = 0;
    for(int i=0; i<N; i++) {
        ll a = v[i].f, b =v[i].s; int cnt = 0;
        while(b) {
            if(b%2) ans = (ans*powBy10[cnt] + a*ones[cnt]) % K;
            cnt++; b/=2;
        }
    }

    cout << ans << '\n';

    return 0;
}

코드 해석

• powBy10, ones 배열을 init하는데 O(1)이 걸린다.
• ans를 구하는데는 여전히 $O(Nlog_2(B))$이지만 상수 계수 C의 값이 1에 가까워지기 때문에 솔브를 받을 수 있었다.

후기

빠른 거듭제곱 알고리즘에 대해서 진득하게 체험해 볼 수 있었던 문제였다.
powBy10과 ones 배열을 생각해내고 이를 내가 원하는 대로 구현하는데 시간이 오래 걸렸다.
그래도 다음부터는 거듭제곱 문제를 비교적 수월하게 풀 수 있을 듯 하다.