백준 34485번: Stacking Cups [C++]

작성일 | In
플래티넘 I 플래티넘 I

문제

Stacking Cups

증명이 많은 그리디 알고리즘 문제입니다.

풀이

가장 큰 컵을 제외하면 나머지 컵들은 자신보다 큰 컵 아래에 놓아서 $2i - 1$만큼 높이거나, 아니면 자신보다 큰 컵 안에 담아서 높이를 높이지 않는 방식으로 사용하지 않는 것과 같은 효과를 낼 수 있습니다.

그렇다면 구간 $[1, 2n - 1]$에 속하는 홀수의 부분집합의 합으로 나타낼 수 없는 수를 알아보면 가장 큰 컵을 놓고 나서 해가 존재하는지 쉽게 알아볼 수 있을 것 같습니다.

실제로 구간 $[1, 2n - 1]$의 홀수를 적절히 골라 합하면 $2$와 $n^2 - 2$를 제외한 $[1, n^2]$의 모든 정수를 나타낼 수 있습니다.

증명

수학적 귀납법으로 증명할 수 있습니다.

먼저 $\displaystyle\sum_{i = 1}^n (2i - 1) = n^2$이므로 하한과 상한은 각각 $1$, $n^2$이 된다는 사실을 짚고 넘어가겠습니다. 해당 명제도 수학적 귀납법으로 증명할 수 있지만 여기서는 생략하겠습니다.

$n = 2$일때 성립합니다.

$1 = 1$, $3 = 3$, $4 = 1 + 3$

$n = k$일때 성립한다고 가정합시다. 그렇다면 $[1, k^2]$에서 $2$와 $k^2 - 2$를 제외한 모든 정수를 만들 수 있습니다.

이미 만들어진 각각의 경우에 대해 $2k + 1$을 더하면 $[1, (k + 1)^2]$에서 $2$, $k^2 - 2$와 $(k + 1)^2 - 2$를 제외한 모든 정수를 만들 수 있습니다.

$2$와 $(k + 1)^2 - 2$가 불가능한 것은 자명합니다.

하지만 $k^2 - 2 = k^2 - (2k - 1) + (2k + 1) - 3 - 1$ 이므로 $k^2 - 2$는 나타낼 수 있습니다.

따라서 $[1, (k + 1)^2]$에서 $2$와 $(k + 1)^2 - 2$를 제외한 모든 정수를 만들 수 있습니다.

가장 큰 컵 놓기

가장 큰 컵이 높이에 $2n - 1$만큼 기여하는 경우를 생각해 봅시다.

$n - 1$개의 컵을 적절히 골라 밑에 두거나 $2n - 1$크기의 컵에 담아서 사용하지 않는 방식으로 $h - (2n - 1)$을 만들 수 있는지는 쉽게 판별할 수 있습니다.

불가능한 경우는 오직 $h - (2n - 1) = 2$ 혹은 $h - (2n - 1) = n^2 - 2$인 경우뿐입니다.

이러한 경우 가장 큰 컵으로 나머지 모든 컵을 담는 방식으로 전체 높이에 1만큼 기여하는 경우를 생각해 볼 수 있습니다.

이때는 $n - 1$개의 컵으로 $h - 1$을 만들 수 있는지 판별하면 됩니다.

$n - 1$개의 컵으로 $h - (2n - 1)$과 $h - 1 $n - 1$를 모두 만들 수 없는 경우는 애초에 해가 없는 경우이므로 다른 경우를 고려하지 않아도 됩니다.

증명

$h - (2n - 1) = n^2 - 2$인 경우는 자명하게 해가 존재하지 않으므로 $h - (2n - 1) = 2$인 경우만 증명하겠습니다.

식을 정리하면 $h = 2n + 1$이고 $h - 1 = 2n$입니다.

  1. 만약 $h - 1 = 2$인 경우
    $n = 1$이고 자명하게 해가 존재하지 않습니다.
  2. 만약 $h - 1 = (n - 1)^2 - 2$인 경우
    $2n = n^2 - 2n - 1$을 만족하는 정수 $n$이 존재하지 않습니다
  3. 만약 $h - 1 > (n - 1)^2$인 경우
    $2n > n^2 - 2n + 1$을 풀면 $n \le 3$이고 세 가지 경우 모두 해가 존재하지 않습니다.
    • $n = 1, h = 3$
    • $n = 2, h = 5$
    • $n = 3, h = 7$

따라서 우리는 가장 큰 컵이 가장 위에 있거나 아래에 있는 경우만 고려해도 됩니다.

여기서 말하는 가장 위에 있다는 뜻은 높이에 기여하지 않는 컵들을 제외했을 때 입니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(_) ((void)0)
#endif
using namespace std;

using ll = long long;

// returns whether h can be represented as
// the sum of a subset of odd numbers in the range [1, 2n - 1]
bool canRepresentWithOdds(ll n, ll h) {
    return h >= 0 and h <= n * n and h != 2 and h != n * n - 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, h;
    cin >> n >> h;

    if (h < 2 * n - 1 or h > n * n) {
        print("impossible");
        return 0;
    }

    vector<ll> stk, rest;

    if (not canRepresentWithOdds(n - 1, h - (2 * n - 1))) {
        if (not canRepresentWithOdds(n - 1, h - 1)) {
            print("impossible");
            return 0;
        }

        print("{} ", 2 * n - 1);
        h--;
    } else {
        stk.push_back(2 * n - 1);
        h -= 2 * n - 1;
    }

    for (ll i = n - 1; i > 0; i--) {
        if (canRepresentWithOdds(i - 1, h - (2 * i - 1))) {
            h -= 2 * i - 1;
            stk.push_back(2 * i - 1);
        } else {
            rest.push_back(2 * i - 1);
        }
    }

    if (h != 0) {
        print("impossible");
        return 0;
    }

    while (not stk.empty()) {
        print("{} ", stk.back());
        stk.pop_back();
    }

    for (ll i : rest)
        print("{} ", i);

    return 0;
}

백준 34485번: Stacking Cups [C++]