티스토리 뷰

 

문제 링크 : https://www.acmicpc.net/problem/14165

 

14165번: Team Building

Every year, Farmer John brings his N cows to compete for "best in show" at the state fair. His arch-rival, Farmer Paul, brings his M cows to compete as well (1≤N≤1000,1≤M≤1000). Each of the N+M cows at the event receive an individual integer score.

www.acmicpc.net

문제를 이해하는데 어려움을 겪었다.

설명에 등장하는 다음 문장

 

That is, each distinct pair (set of KK cows for FJ, set of KK cows for FP) where FJ wins should be counted.

 

에서 등장하는 KK 는 K의 오타로 보인다. 

 

문제에서 요구하는 바를 요약하자.

 

문제에 등장하는 두 사람이 가진 집합(소들의 집합) A, B 각각에서  k개의 원소를 가지는 부분 집합 X, Y를 선택한다.

X={x1,x2,,xk},Y={y1,y2,,yk}

 

이렇게 선택한 집합의 쌍 ( X, Y )들 중에서

x1x2xk

y1y2xk

내림차순으로 정렬했을 때,

(집합은 순서를 고려하지 않으므로 크기 순으로 혹은 크기 역순으로 정렬해도 관계없다.)

다음의 조건을

x1>y1,x2>y2,,xk>yk.

을 만족하는 쌍의 개수를 구하는 문제이다.

 

원래의 두 집합 A, B를 크기 역순으로 정렬하고 시작하면 편하다.

재귀함수 recur( i , j , len ) 는 집합 A의 i 번째, 집합 B의  j 번째 원소에서부터 len 크기의 부분 집합 쌍이 조건을 만족하는 경우의 수이다.

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

const ll mmod=1e9+9;

int n,m,k;
ll arr[1001], brr[1001];
ll dp[1001][1001][11];

ll recur(int i, int j, int len){
    if(len==0) return 1;
    if(i==n or j==m) return 0;
    
    ll &ret=dp[i][j][len];
    if(ret!=-1) return ret;
    
    ret=recur(i+1, j, len)+recur(i,j+1,len)-recur(i+1,j+1, len); // 중복을 처리
    ret=(ret+mmod)%mmod;
    
    if(arr[i]>brr[j]) ret=(ret+recur(i+1, j+1, len-1))%mmod;
    return ret;
}

int main(){
    scanf("%d%d%d", &n,&m,&k);
    for(int i=0;i<n;i++) scanf("%lld", &arr[i]);
    for(int j=0;j<m;j++) scanf("%lld", &brr[j]);
    
    sort(arr, arr+n, [](ll x, ll y){return x>y;});
    sort(brr, brr+m, [](ll x, ll y){return x>y;});
    
    memset(dp,-1, sizeof dp);
    printf("%lld\n", recur(0,0,k));
}

 

이 코드에서는 arr, brr 을 크기 역순으로 정렬했지만 위에서 언급한 것처럼 크기 순으로 정렬해도 문제가 생기지 않는다.

반응형
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/07   »
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
글 보관함