백준 11876번 PERICA

문제 링크입니다: https://www.acmicpc.net/problem/11876

수학적으로 접근해야하는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 핵심은 주어진 키 값들을 오름차순으로 정렬하고 해당 키가 몇 번 눌리는지를 구하는 것이였습니다.

2. v[i]보다 작은 키들이 i - 1개이므로 v[i]가 눌리는 횟수는 i - 1개의 키들 중 k - 1개를 선택하는 조합입니다. 

-> (i - 1Ck - 1)

3. 따라서, k - 1Ck - 1 ~ n - 1Ck - 1의 합을 더해주면 답이 됩니다.

N의 최대값이 100,000이고 K의 최대값은 50이기 때문에 DP로 조합을 구해도 상관이 없지만,

시간복잡도를 낮추기 위해 연두님이 팀노트에 작성하셨듯이 역원을 이용해 O(N) 안에 조합을 구할 수 있습니다.

(https://blog.naver.com/pasdfq/221313420634)

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 100000 + 1;

const int MOD = 1000000000 + 7;

 

int N, K;

vector<pair<int, int>> v;

long long cache[MAX][50 + 1];

 

//dp를 이용하여 조합 구하기

void calc(void)

{

        cache[0][0] = 1;

 

        for (int i = 1; i <= N; i++)

        {

                 cache[i][0] = 1;

                 for (int j = 1; j <= K; j++)

                         cache[i][j] = cache[i - 1][j] % MOD + cache[i - 1][j - 1] % MOD;

        }

}

 

//inv -> inverse

long long inv[MAX], factorial[MAX], factorialInv[MAX];

//O(N)으로 조합을 구하는 방법 출처: blog.naver.com/pasdfq

void init(int N)

{

        factorial[1] = 1;

        for (int i = 2; i <= N; i++)

                 factorial[i] = (factorial[i - 1] * i) % MOD;

 

        inv[1] = 1;

        for (int i = 2; i <= N; i++)

                 inv[i] = (MOD - MOD / i)*inv[MOD%i] % MOD;

 

        factorialInv[1] = 1;

        for (int i = 2; i <= N; i++)

                 factorialInv[i] = (factorialInv[i - 1] * inv[i]) % MOD;

}

 

long long combination(int n, int r)

{

        if (r == 0 || n == r)

                 return 1;

 

        return (((factorial[n] * factorialInv[r]) % MOD) * factorialInv[n - r]) % MOD;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> K;

 

        //init(N);

        calc();

        for (int i = 0; i < N; i++)

        {

                 int num;

                 cin >> num;

 

                 v.push_back({ num, i });

        }

        sort(v.begin(), v.end());

 

        long long result = 0;

        for (int i = K - 1; i < N; i++)

        {

                 result += (v[i].first * cache[i][K-1]) % MOD;

                 result %= MOD;

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~