BOJ 24337 : 가희와 탑

• 문제 링크 : boj.kr/24337
• 난이도 : G3
• 태그 : 그리디, 해 구성하

24337번: 가희와 탑

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, a, b;
    cin >> n >> a >> b;

    if(a + b - 1 > n) {
        cout << -1;
        return 0;
    }
    if(a == 1) cout << b << " ";
    for(int i = 0; i < n - (a+b-1); i++) {
        cout << "1 ";
    }
    for(int i = 1; i < a; i++) {
        cout << i << " ";
    }
    if(a > b) cout << a << " ";
    else if(a != 1) cout << b << " ";
    for(int i = b-1; i >= 1; i--) {
        cout << i << " ";
    }
    return 0;
}

---

풀이

가장 높은 건물은 가희와 단비 모두에게 보일 것이다.

사전 순으로 앞서려면 이 가장 높은 건물이 가능한 작아야 한다. 따라서 가장 높은 건물은 a와 b중 더 큰 값 t를 높이로 갖는다.

이제 n개의 건물을 놓는 것이 아닌 가능한 최소의 건물을 사전 순으로 가장 앞서도록 놓아보자.

a, b 중 큰 쪽에는 1부터 t-1까지의 높이를 갖는 건물들을 늘어놔야 한다. 작은 쪽 역시 1부터 필요한 만큼 늘어놓는다. 사전 순으로 앞서기 위해서는 작은 수를 사용해야 하기 때문이다.

 

가능한 최소의 건물을 놓았다면, 이제 나머지의 건물을 채워야 한다.

가장 단순하게 생각해보면, 사전 순으로 앞선다는 것은 작은 수들이 앞에 놓여있다는 것을 의미하고, 가장 앞에 1들을 늘어놓는 것이 가장 사전 순으로 앞선다는 것을 알 수 있다.

단, a가 1인 경우에는 앞에 1을 놓을 수 없으므로, 예외 처리를 잘 해주어야 한다.