COFO::1288C Two Arrays

• Link : COFO::1288C
• dp reference youtubue

Problem

• level : 1600
• tag : combinatorics, dp
• TIME
  • to understand :
  • to algorithm : fail
  • to code :
  • to debug :
  • understanding edit : 40

Point

• n과 m이 주어집니다.
• 다음의 조건을 만족하는 배열 a, b 의 조합의 갯수를 구하시오
  • a, b 의 각 길이는 m
  • a, b 에 속한 원소는 1이상 n이하
  • a[i] <= b[i] 를 만족
  • a는 증가함수
  • b는 감소함수

Design

• dp로 푸는방법의 asc 배열은 구했지만 dsc 배열을 구하질 못했었습니다.
• dp가 아직 어려워서, 문제를 처음보자마자 dp구나! 는 떠올리기 어려웠고,
• 그나마 숫자 몇개를 손으로 써보며 식이 성립된다는 사실을 알게되어 asc 를 구할 수 있었습니다.
• 그럼 간단하게 asc와 dsc dp 의 정의에 대해 정리해보겠습니다.
  • asc[i][j] : 배열의 길이가 i이고, 해당 배열에서 가장 큰 값이 j이고, non-decreasing하는 배열의 갯수
    • asc[i][j] 는 마지막 값이 j인 배열을 의미합니다.
      • …. j 가 되겠죠.
      • 그럼 이때, j바로 앞에 오는 수는 어떤 것들이 있을까요? 1 부터 j가 있겠죠.
    • 이를 다시 정리하면, asc[i][j] = asc[i-1][1] + asc[i-1][2] + … + asc[i-1][j-1] + asc[i-1][j]가 됩니다.
  • 식으로 정리하면, asc[i][j] = asc[i][j-1] + asc[i-1][j] 가 됩니다.
  • dsc[i][j] : 배열의 길이가 i이고, 해당 배열의 모든 값이 j이하인 배열의 갯수
    • dsc[i][j] 는 마지막 값이 j인 배열을 의미합니다.
    • 그럼 이는, 다음과 같이 정리됩니다.
    • dsc[i][j] = asc[i][1] + asc[i][2] + … + asc[i][j-1] + asc[i][j]
      • 이렇게 표현된다는건, descending을 ascending을 통해 거꾸로 표현하는 방법입니다.
    • dsc[i][j] = dsc[i][j-1] + asc[i][j]가 됩니다.
• 해당 풀이 말고도 edit은 단순히 xCy 즉, 조합론으로 한줄만에 풀이합니다.
• 아이디어가 좋으니 기억해두면 좋을 것 같습니다.
• b의 순서를 거꾸로 뒤집어서 a의 뒤에다가 붙여놓으면, 이제 통째로 non-descending order를 가지게 됩니다.
  • 즉, 배열의 길이가 2m이 되었고, 각 원소는 1과 n사이의 숫자를 가지게 됩니다.
• 따라서, (2m + n - 1) 개 중에 (2m)개를 선택하는 풀이로 정리할 수 있습니다.
  • 이유는 명확히 이해가 되지 않네요
  • 조합론으로 풀이한 사람도 거의 없고, 유튜브 영상도 없는 상황이라 추후에 이해되는대로 업데이트해야겠네요

Complexity

• O(NM)

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;
ll MOD = 1e9 + 7;
ll asc[11][1001]; // asc[i][j] : max(a) = j이고, 길이가 i일때 non-decreasing의 갯수 % 1e9 + 7
ll dsc[11][1001]; // dsc[i][j] : max(a) = j이고, 길이가 i일때 non-increasing의 갯수 % 1e9 + 7

int n, m;
void solve(){
    cin >> n >> m;
    rep(j, 1, n + 1) asc[1][j] = 1;
    rep(i, 2, m + 1) rep(j, 1, n+1) asc[i][j] = (asc[i-1][j] + asc[i][j-1]) % MOD;
    rep(i, 1, m + 1) rep(j, 1, n+1) dsc[i][j] = (dsc[i][j-1] + asc[i][j]) % MOD;
    
    
    ll ans = 0;
    rep(i, 1, n + 1)
        ans = (ans + asc[m][i] * dsc[m][n - i + 1]) % MOD;
    
    cout << ans << '\n';
}
int main(){
    freopen("input.txt", "r", stdin);
    //int tc; cin >> tc;
    //while(tc--)
        solve();
    return 0;
}