2018년 노르딕 대학생 프로그래밍 콘테스트(NCPC 2018)의 문제들을 정리한 풀이 노트입니다. 각 문제의 핵심 아이디어와 구현 방식을 다룹니다.

A. 개구리 탈출

n마리의 개구리가 우물에 빠졌습니다. 각 개구리는 점프력, 체중(하부 지지 한도), 신장을 가지며, 서로를 밟고 올라가 우물을 탈출해야 합니다. 최대 몇 마리가 탈출할 수 있는지 구하는 문제입니다.

지지 한도가 큰 개구리부터 아래에 위치해야 하므로, 지지 한도를 기준으로 내림차순 정렬합니다. 이후 배낭 DP를 적용하며, height[j]는 누적 체중 j일 때 달성 가능한 최대 높이를 의미합니다. 상태 전이는 height[j] = max(height[j], height[j + weight] + stature)로 표현됩니다.

#include <bits/stdc++.h>
using namespace std;

struct Amphibian {
    int leap, load, stature;
    bool operator<(const Amphibian& o) const {
        return load > o.load;
    }
};

const int LIM = 1e8 + 5;
Amphibian frogs[100005];
int reach[LIM];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, wellDepth;
    cin >> n >> wellDepth;
    
    for (int i = 0; i < n; i++) {
        cin >> frogs[i].leap >> frogs[i].load >> frogs[i].stature;
    }
    sort(frogs, frogs + n);
    
    int escaped = 0;
    for (int i = 0; i < n; i++) {
        int w = frogs[i].load;
        for (int j = 1; j < w && j + w < LIM; j++) {
            reach[j] = min(wellDepth + 2, max(reach[j], reach[j + w] + frogs[i].stature));
        }
        if (reach[w] + frogs[i].leap > wellDepth) escaped++;
    }
    cout << escaped << "\n";
    return 0;
}

B. 순열 검증

n개의 항목이 1부터 n까지의 숫자로 이루어져 있는지, 혹은 "mumble"이라는 문자열이 적절히 배치되어 있는지 확인합니다. 단순 순회로 해결 가능합니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    bool valid = true;
    
    for (int i = 1; i <= n; i++) {
        string token;
        cin >> token;
        if (token[0] == 'm') continue;
        int val = stoi(token);
        if (val != i) valid = false;
    }
    
    cout << (valid ? "makes sense" : "something is fishy") << "\n";
    return 0;
}

C. 쓰레기 수거

n일 동안 쓰레기가 쌓이며, 연속된 날짜의 쓰레기 누적량이 20 이상이 되기 전날 청소를 해야 합니다. 최소 청소 횟수를 구합니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> days(n);
    for (int& x : days) cin >> x;
    
    int sweeps = 0;
    vector<bool> cleaned(400, false);
    
    for (int cur = 1; cur <= 385; cur++) {
        int pile = 0;
        for (int d : days) {
            if (d > cur) break;
            if (cleaned[d]) continue;
            pile += cur - d;
            if (pile >= 20) {
                sweeps++;
                for (int k = 1; k < cur; k++) cleaned[k] = true;
                break;
            }
        }
    }
    cout << sweeps << "\n";
    return 0;
}

D. 피자 배달

그래프 상에서 피자 배달원이 여러 주문을 동시에 처리할 수 있을 때, 고객 대기 시간의 최댓값을 최소화하는 문제입니다. 먼저 다익스트라로 전체 최단거리를 계산하고, 대기 시간에 대해 이분 탐색을 수행합니다. DP로 구간별 배달 경로를 검증하며, dp[u]는 u번째 주문까지 처리하고 출발점으로 돌아오는 최소 시간을 의미합니다.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = (1LL << 60);

struct Edge {
    int to, w, nxt;
};

struct Order {
    int place, ready, ordered;
};

vector<Edge> edges;
vector<int> graph[1005];
ll dist[1005][1005];
ll memo[1005];
Order reqs[1005];

void dijkstra(int src, int n) {
    fill(dist[src] + 1, dist[src] + n + 1, INF);
    dist[src][src] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    pq.push({0, src});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[src][u]) continue;
        for (int e : graph[u]) {
            int v = edges[e].to;
            ll nd = d + edges[e].w;
            if (nd < dist[src][v]) {
                dist[src][v] = nd;
                pq.push({nd, v});
            }
        }
    }
}

bool feasible(ll limit, int q) {
    fill(memo, memo + q + 1, INF);
    memo[0] = 0;
    
    for (int i = 0; i < q; i++) {
        ll route = 0, earliest = memo[i];
        ll slack = INF;
        for (int j = 1; i + j <= q; j++) {
            int idx = i + j;
            if (j == 1) route += dist[1][reqs[idx].place];
            else route += dist[reqs[idx-1].place][reqs[idx].place];
            
            earliest = max(earliest, (ll)reqs[idx].ready);
            if (earliest + route - reqs[idx].ordered > limit) break;
            
            slack = min(slack, limit + reqs[idx].ordered - route);
            if (slack < earliest) break;
            memo[idx] = min(memo[idx], earliest + route + dist[reqs[idx].place][1]);
        }
    }
    return memo[q] < INF;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, q;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({v, w, (int)graph[u].size()});
        edges.push_back({u, w, (int)graph[v].size()});
        graph[u].push_back(edges.size() - 2);
        graph[v].push_back(edges.size() - 1);
    }
    
    for (int i = 1; i <= n; i++) dijkstra(i, n);
    
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> reqs[i].ordered >> reqs[i].place >> reqs[i].ready;
    }
    
    ll lo = 0, hi = (ll)1e15, ans = 0;
    while (lo <= hi) {
        ll mid = (lo + hi) / 2;
        if (feasible(mid, q)) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    cout << ans << "\n";
    return 0;
}

E. 확률 전투

아군 n명, 적군 m명이 있고 매 턴 살아있는 개체 중 하나에게 1데미지를 입힙니다. 정확히 d번 공격 후 적군 전멸 확률을 구합니다. 남은 체력 분포를 기록하며 메모이제이션으로 해결합니다.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll power[15];
int allyHP[7], enemyHP[7];
unordered_map<ll, double> cache;

ll encode(const int stat[]) {
    ll code = 0;
    for (int i = 12; i >= 1; i--) {
        code = code * 10 + stat[i];
    }
    return code;
}

void decode(ll code, int stat[]) {
    for (int i = 1; i <= 12; i++) {
        stat[i] = code % 10;
        code /= 10;
    }
}

double solve(ll state, int remain) {
    if (cache.count(state)) return cache[state];
    if (state < power[7]) return cache[state] = 1.0;
    if (remain == 0) return cache[state] = 0.0;
    
    int cur[15] = {0};
    decode(state, cur);
    
    int alive = 0;
    for (int i = 1; i <= 12; i++) alive += cur[i];
    
    double res = 0;
    for (int i = 1; i <= 12; i++) {
        if (cur[i] == 0) continue;
        ll nxt = state - power[i];
        if (i != 7 && i != 1 && cur[i] > 1) nxt += power[i-1];
        res += (double)cur[i] / alive * solve(nxt, remain - 1);
    }
    return cache[state] = res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, d;
    cin >> n >> m >> d;
    
    int total = 0;
    for (int i = 1; i <= n; i++) cin >> allyHP[i], total += allyHP[i];
    for (int i = 1; i <= m; i++) cin >> enemyHP[i], total += enemyHP[i];
    
    if (d >= total) {
        cout << fixed << setprecision(7) << 1.0 << "\n";
        return 0;
    }
    
    power[1] = 1;
    for (int i = 2; i <= 13; i++) power[i] = power[i-1] * 10;
    
    ll init = 0;
    for (int i = m; i >= 1; i--) init += power[6 + enemyHP[i]];
    for (int i = n; i >= 1; i--) init += power[allyHP[i]];
    
    cout << fixed << setprecision(7) << solve(init, d) << "\n";
    return 0;
}

H. 잔디깎기 기계

정원 면적과 여러 잔디깎기 기계의 정보가 주어질 때, 1주일 내에 전체를 처리할 수 있는 가장 저렴한 기계들을 출력합니다. 작업-충전 주기를 고려한 실제 처리량을 계산합니다.

#include <bits/stdc++.h>
using namespace std;

struct Mower {
    string name;
    int cost, rate, work, charge, seq;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int gardenLen, cnt;
    cin >> gardenLen >> cnt;
    
    vector<Mower> list;
    for (int i = 0; i < cnt; i++) {
        string line;
        cin >> line;
        stringstream ss(line);
        string token;
        vector<string> parts;
        while (getline(ss, token, ',')) parts.push_back(token);
        
        Mower m;
        m.name = parts[0];
        m.cost = stoi(parts[1]);
        m.rate = stoi(parts[2]);
        m.work = stoi(parts[3]);
        m.charge = stoi(parts[4]);
        m.seq = i;
        list.push_back(m);
    }
    
    sort(list.begin(), list.end(), [](const Mower& a, const Mower& b) {
        return a.cost < b.cost;
    });
    
    int best = INT_MAX;
    for (const auto& m : list) {
        double cycles = 10080.0 / (m.work + m.charge);
        double coverage = cycles * m.rate * m.work;
        if (coverage >= gardenLen) {
            if (best == INT_MAX || best == m.cost) {
                cout << m.name << "\n";
                best = m.cost;
            }
        }
    }
    if (best == INT_MAX) cout << "no such mower\n";
    return 0;
}

I. 대표단 선발

정확히 합계 S를 만들기 위해 필요한 최소 인원과 그 구성을 출력합니다. 각 후보의 가치는 이전 것의 2 이하라는 조건이 보장되어, 그리디로 해결됩니다. Java의 BigInteger로 큰 수를 처리합니다.

import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        BigInteger target = sc.nextBigInteger();
        
        Map<BigInteger, String> names = new HashMap<>();
        List<BigInteger> values = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            String name = sc.next();
            BigInteger val = sc.nextBigInteger();
            names.put(val, name);
            values.add(val);
        }
        
        values.sort(Collections.reverseOrder());
        List<String> picked = new ArrayList<>();
        
        for (BigInteger v : values) {
            if (target.compareTo(v) >= 0) {
                picked.add(names.get(v));
                target = target.subtract(v);
            }
        }
        
        if (target.signum() != 0) {
            picked.clear();
        }
        
        System.out.println(picked.size());
        for (String s : picked) {
            System.out.println(s);
        }
        sc.close();
    }
}

J. 이진 문자열 설계

00, 01, 10, 11 쌍의 개수로부터 원본 01 문자열을 복원합니다. 0과 1의 개수를 조합수로 유추하고, 1을 왼쪽에 몰아넣은 후 적절히 0을 삽입하여 조건을 만족시킵니다.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    
    if (a == 0 && b == 0 && c == 0 && d == 0) {
        cout << "1\n";
        return 0;
    }
    
    ll n0 = 0, n1 = 0;
    if (a >= 2) {
        n0 = (ll)sqrt(2 * a) + 1;
        if (n0 * (n0 - 1) != 2 * a) { cout << "impossible\n"; return 0; }
    } else if (a == 1) n0 = 2;
    else if (b != 0 || c != 0) n0 = 1;
    
    if (d >= 2) {
        n1 = (ll)sqrt(2 * d) + 1;
        if (n1 * (n1 - 1) != 2 * d) { cout << "impossible\n"; return 0; }
    } else if (d == 1) n1 = 2;
    else if (b != 0 || c != 0) n1 = 1;
    
    if (n0 * n1 != b + c) { cout << "impossible\n"; return 0; }
    
    vector<int> result;
    int made = 0;
    while (made < b) {
        if (b - made >= n1) {
            result.push_back(0);
            n0--;
            made += n1;
        } else {
            int shift = n1 - (b - made);
            for (int i = 0; i < shift; i++) result.push_back(1);
            n1 -= shift;
            result.push_back(0);
            n0--;
            made = b;
            break;
        }
    }
    while (n1-- > 0) result.push_back(1);
    while (n0-- > 0) result.push_back(0);
    
    for (int x : result) cout << x;
    cout << "\n";
    return 0;
}

K. 나무 색칠

n개 노드로 된 트리를 정확히 k가지 색으로 칠하는 방법의 수를 구합니다. 인접한 노드는 색이 달라야 합니다. 최대 k색 사용 가능한 경우의 수를 구하고, 포함-배제 원리로 정확히 k색 사용 경우를 도출합니다.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MOD = 1e9 + 7;

ll fact[2505];

ll modpow(ll base, int exp) {
    ll res = 1;
    while (exp > 0) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

ll nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * modpow(fact[r], MOD - 2) % MOD * modpow(fact[n - r], MOD - 2) % MOD;
}

ll waysWith(int k, int n) {
    return (ll)k * modpow(k - 1, n - 1) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    
    fact[0] = 1;
    for (int i = 1; i <= k; i++) fact[i] = fact[i-1] * i % MOD;
    
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
    }
    
    ll ans = 0;
    int sign = 1;
    for (int i = k; i >= 1; i--) {
        ll term = waysWith(i, n) * nCr(k, i) % MOD;
        if (sign > 0) ans = (ans + term) % MOD;
        else ans = (ans - term + MOD) % MOD;
        sign = -sign;
    }
    cout << ans << "\n";
    return 0;
}