티스토리 뷰
문제 링크 : 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, Y )들 중에서
내림차순으로 정렬했을 때,
(집합은 순서를 고려하지 않으므로 크기 순으로 혹은 크기 역순으로 정렬해도 관계없다.)
다음의 조건을
을 만족하는 쌍의 개수를 구하는 문제이다.
원래의 두 집합 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 을 크기 역순으로 정렬했지만 위에서 언급한 것처럼 크기 순으로 정렬해도 문제가 생기지 않는다.
'DS\Algo > Dynamic Programming' 카테고리의 다른 글
BOJ 11066 Merging Files(파일 합치기) (0) | 2022.09.14 |
---|---|
BOJ 11048 이동하기 (0) | 2022.09.11 |
BOJ 11054 가장 긴 바이토닉 부분 수열 (0) | 2022.09.09 |
BOJ 11052 카드 구매하기 (0) | 2022.09.09 |
BOJ 13448 SW 역량 테스트 (0) | 2022.08.21 |
- Total
- Today
- Yesterday
- python3
- nearest common ancestor
- Reference
- number theory
- bash
- BOJ
- dynamic programming
- bash script
- 정수론
- persistent segment tree
- lazy propagation
- 다익스트라
- max flow
- 백준
- Aho-Corasick
- Dijkstra
- map
- script
- fenwick tree
- RUBY
- C++ big number
- shell
- Shell Programming
- stack
- segment tree
- 세그먼트 트리
- Vim
- math font
- javascript array
- JavaScript
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |