[BOJ 16890] 창업

문제 링크

https://www.acmicpc.net/problem/16890

16890번: 창업

 

 

 

---

아이디어

게임의 진행은 구사과부터 순서대로 한 턴씩 진행되기 때문에 게임이 N턴 뒤에 끝난다고 할 때,

구사과는 (N + 1) / 2 번의 턴을, 큐브러버는 N / 2번의 턴을 갖는다

 

 

구사과는 사전순으로 가장 앞서는 문자열을 만들고 싶어 하므로

갖고 있는 n개의 알파벳 중에서 작은 순서대로 (n+1) / 2 개의 알파벳만을 사용해야 한다

마찬가지로 큐브러버는 사전순으로 가장 뒤에 오는 문자열을 만들고 싶어 하므로

갖고 있는 n개의 알파벳 중에서 큰 순서대로 n / 2개의 알파벳만을 사용해야 한다

(이는 귀류법으로 증명할 수 있을 것이다)

 

 

구사과

이제 구사과의 입장에서 생각해보자

구사과는 사전순으로 가장 앞서는 문자열을 만들고 싶다

1. 구사과가 갖고있는 가장 작은 알파벳보다 큐브러버가 갖고있는 가장 큰 알파벳이 더 크다면

   구사과는 가장 작은 알파벳을 완성시킬 문자열의 비어있는 맨 앞 칸에 놓아야 한다

   그렇지 않으면 다음 턴에 큐브러버가 그 칸을 자신이 갖고 있는 가장 큰 알파벳으로 채울 것이다

 

2 구사과가 갖고있는 가장 작은 알파벳보다도 큐브러버가 갖고있는 가장 큰 알파벳이 더 작다면

  구사과는 굳이 완성시킬 문자열의 앞을 채울 필요가 없다

  따라서 구사과가 갖고있는 알파벳 중 가장 큰 알파벳을 완성시킬 문자열의 가장 뒤에 채운다

 

큐브러버

큐브러버의 입장에서도 이와 같은 로직을 갖는다

1. 구사과가 갖고있는 가장 작은 알파벳보다 큐브러버가 갖고있는 가장 큰 알파벳이 더 크다면

   큐브러버는 가장 큰 알파벳을 완성시킬 문자열의 비어있는 맨 앞 칸에 놓아야 한다

   그렇지 않으면 다음 턴에 구사과가 그 칸을 자신이 갖고 있는 가장 작은 알파벳으로 채울 것이다

 

2. 구사과가 갖고있는 가장 작은 알파벳보다도 큐브러버가 갖고있는 가장 큰 알파벳이 더 작다면

    큐브러버는 굳이 완성시킬 문자열의 앞을 채울 필요가 없다 (오히려 작아진다)

    따라서 큐브러버가 갖고있는 알파벳 중 가장 작은 알파벳부터 완성시킬 문자열의 가장 뒤에 채운다

 

 

---

소스코드

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int MN = 300030;
char a[MN], b[MN], ans[MN];
vector<char> k, c;
int main()
{
    scanf("%s", a);
    scanf("%s", b);

    int l = strlen(a);
    k.resize(l), c.resize(l);
    for (int i = 0; i < l; ++i) {
        k[i] = a[i];
        c[i] = b[i];
    }
    sort(k.begin(), k.end());
    sort(c.begin(), c.end());

    int turn = 0;
    int kl = 0, kr = (l + 1) / 2 - 1;
    int cl = (l + 1) / 2, cr = l - 1;
    int al = 0, ar = l - 1;

    while (turn < l) {
        if (turn & 1) { // cubelover
            if (k[kl] < c[cr]) { 
                ans[al] = c[cr];
                al++; cr--;
            }
            else {
                ans[ar] = c[cl];
                ar--; cl++;
            }
        }
        else { // koosaga
            if (k[kl] < c[cr]) {
                ans[al] = k[kl];
                al++; kl++;
            }
            else {
                ans[ar] = k[kr];
                ar--; kr--;
            }
        }
        turn++;
    }
    
    printf("%s", ans);
    return 0;
}

 

 

 

 

 

공부한 것을 정리하기 위한 기록입니다.

틀린 부분이 있다면 부드럽게 알려주세요.