[SW Expert Academy] 4701. 경시대회 매니저의 고민

4701. 경시대회 매니저의 고민

SW Expert Academy의 문제들은 저작권이 있기 때문에 링크로 대체합니다!

클릭시 이동합니다!!

어떻게 풀까?

이 문제는 경우의 수를 구하는 문제입니다!

전에 있던 경우의 수가 어떻게 해서 다음의 경우의 수에 영향을 줄지 잘 생각해서, 이를 점화식으로 표현하는 것이 중요합니다.

더 간단히 요약하면, DP라는 것이죠!

과연, 이전의 어떤 경우에서 DP를 구할 수 있을까요!?

자! 홈페이지의 테스트 케이스 1 번을 가지고 연구를 하겠습니다!

자! 이제 어떻게 답을 찾아가는지 생각해봅시다!

 

우선, 위와 같은 상황에서 디피를 만들면 이전에 뽑은 수들을 하나하나 다시 비교하면서 승점이 어떻게 되는지 확인하려면, 정렬을 하는것이 좋아보입니다.

왜냐하면, 정렬을 한 상태라면 '이전에 뽑은 수들보다 큰 수이다' 라는 것이 보장되고, 이전 수들을 모두 이기는 훌륭한 선수라는 것이기 때문이죠!

정렬을 하지 않은 상태라면, 이전에 구성됬던 숫자들이 지금 뽑은 숫자보다 높은 숫자인지 낮은 숫자인지도 계속 확인해봐야 할 것입니다!

그럼, '이전의 경우가 다음 경우에 어떻게 영향을 줄 수 있을까?' 를 알아보겠습니다.

원하는 방법은, 해당 점수를 포함하여 보다 낮은 점수와의 승, 패를 가리는 것을 보는 것입니다!

글로 보기만 하면 뭔가 이해가 잘 안됩니다!

예를 들면 이런식인 겁니다! 36이 이기는 경우의 수를 확인해 봅시다!

확인할 수는 아래와 같을 것입니다.

우선, 36 한 명을 선택했을 경우를 봅시다!

36 - 13, 36 - 19로 1승을 할 수 있는 경우가 2개가 됩니다!

이번에는 36을 포함하여 2명을 선택했을 경우를 봅시다!

문제에서는 상대팀이 고정되어있다고 했죠!

그럼 경우의 수는,

4  36

13 19

36 4

13 19

16 36

13 19

36 16

13 19

이렇게 4 가지가 나올 것입니다! 1 승이 2개 2승이 2개이군요!

그런데, 한 가지 재밌는 사실을 볼 수 있습니다!

다시 한 번 36이 선택됐을 때를 확인해 봅시다!

우선, 36을 선택하면, 모든 선수들의 점수가 정렬되어있기 때문에, 2 팀의 누구와 겨루더라도 36이 이긴다는 것을 확인할 수 있습니다!

즉, 

4 36

13 19 와 같은 경우의 수는

이전에 

4

13

을 골랐던 경우의 수에다가 13을 제외한 나머지 2팀의 팀원들과 36을 매칭 시키는 것이라고 할 수 있죠!

하지만, 4와 13, 그리고 나머지 2팀의 팀원들이 어떤 수인지는 전혀 중요하지 않습니다! 왜냐하면, 어짜피 36이 제일 큰 수이기 때문이죠!

남은 수가 무엇이든, 36은 모두 이길 수 있습니다.

또한, 앞에서부터 차례 차례 계산했던 것들을 저장한다고 한다면, 36을 넣기전에 1명을 선택했을 경우에 대한 수는 모두 저장되어있을 것입니다!

만약 1팀의 어떤 선수 x를 포함하여 j+1 명을 선택했을 때의 k+1번 승리한 경우의 수가 알고싶다면, 

가장 중요한 것은 2 팀의 팀원의 수와 j 명을 선택했을때의 의 k번 승리한 경우의 수를 알아내는 것이죠!

어떤 선수 x를 포함하여 j + 1명을 선택했을 때의 k + 1번 승리한 경우의 수는,

현재 어떤 선수 x보다 점수가 낮은 2팀의 팀원 - j 에다가 j 명을 선택했을 떄의 k번 승리한 경우의 수를 곱하면 되겠죠! 

그림으로 정리하죠!

만약, 2팀의 선수를 기준으로 보면 어떨까요???

2팀의 선수를 기준으로 보면, 1팀의 선수는 무조건 지기 때문에, 승점이 오르지 않습니다. 따라서,

j+1명을 선택했을 때 k번 이기는 경우의 수 += j명을 선택했을 때 k 번 이기는 수 * (1 팀의 인원수 - j) 가 되겠죠!

이렇게 생각하면, 이제 2차원 배열을 통해서 해당 점수를 저장할 수 있다는 생각이 듭니다!

또한, 1팀과 2팀을 합쳐서 정렬을 한 뒤에 한명 한명씩 뽑아서, 

뽑은 사람이 1팀인가 2팀인가에 따라서 선택과 승점에 대한 2차원 배열을 채워갑시다!

그럼 정답은 어디에 있을까요????

n명을 선택해야 정답이기 때문에, 배열의 n번째 행의 0번부터 n번 열까지가 바로 정답구간이 될 것입니다!!!!!!!!!!!

코드

//https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWR8UbE6-1ADFAUr
 
#include<cstdio>
#include<cstring>
 
struct info {
    int rate, team;
};
info rate[201];
info temp[201];
 
void mergeSort(int le, int m, int ri) {
    int l = le, k = le, r = m + 1;
 
    while (l <= m && r <= ri) {
        temp[k++] = rate[l].rate < rate[r].rate ? rate[l++] : rate[r++];
    }
    while (l <= m) temp[k++] = rate[l++];
    while (r <= ri) temp[k++] = rate[r++];
 
    int len[2] = { 0, 0};
    for (int i = le; i <= ri; i++) {
        
        rate[i] = temp[i];
    }
}
 
void merge(int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        merge(l, m);
        merge(m + 1, r);
        mergeSort(l, m, r);
    }
}
 
const int MOD = 1000000007;
long long pro[101][101];
int size[2];
 
 
void swap(int &i1, int &i2, int *ind) {
    int temp = ind[i1];
    ind[i1] = ind[i2];
    ind[i2] = temp;
}
 
int ManagerWorry() {
    int t;
    scanf("%d\n", &t);
    for (int tc = 1; tc <= t; tc++) {
        int n;
        scanf("%d\n", &n);
 
        int t;
 
        for (int i = 0; i < n; i++) {
            scanf("%d\n", &t);
            rate[i].rate = t;
            rate[i].team = 0;
        }
        for (int i = n; i < 2 * n; i++) {
            scanf("%d\n", &t);
            rate[i].rate = t;
            rate[i].team = 1;
        }
 
        merge(0, 2 * n - 1);
        memset(pro, 0, sizeof(pro));
 
        size[0] = size[1] = 0;
        pro[0][0] = 1;
 
        for (int i = 0; i < 2 * n; i++) {
            int nt = rate[i].team;
            size[nt]++;
 
            for (int j = n - 1; j >= 0; j--) {
                for (int k = 0; k < n; k++) {
                    if (pro[j][k]) {
                        int remains = size[nt ^ 1] - j;
 
                        if (remains) {
                            pro[j + 1][k + (nt ^ 1)] = ((pro[j + 1][k + (nt ^ 1)] + pro[j][k] * remains)) % MOD;
                        }
                    }
                }
            }
        }
 
        printf("#%d ", tc);
        for (int i = 0; i <= n; i++) {
            printf("%lld ", pro[n][i]);
        }
        printf("\n");
 
    }
    return 0;
}

여담

정말 어려웠습니다!

실은 저도 점화식 못찾았습니다. ㅎㅎ

꼬박 1주일간 점화식을 찾았는데,

비슷한 식으로 만들긴 했지만, 핵심적인 부분을 몇가지 놓쳐서 결국 찾지 못했네요!

이런 경우의 수는 점화식을 빨리 찾는사람이 승자라는 사실! 잊지마세용

시간복잡도는 입니다.