[백준/BOJ] 11051번 : 이항 계수 2, 9375번 : 패션왕 신해빈, 2004번 : 조합 0의 개수 (조합, 경우의 수)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 11051번 : '이항 계수 2', 9375번 : '패션왕 신해빈', 2004번 : '조합 0의 개수' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Silver 티어에 해당하며, 문제를 풀이하기 위해 조합론과 경우에 수에 대한 배경 지식이 있으면 좋습니다.

 

 

11051번 : 이항 계수 2

 

단순히 N Combination K를 구하는 문제입니다.

다만 N이 최대 1000까지 주어질 수 있으므로 10007로 나눈 나머지를 구해주면 되며, 시간 초과를 방지하기 위해 DP를 활용하여 계산해주어야 합니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int comb[1005][1005] = {1, 0};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, K; cin >> N >> K;
    for(int i=1; i<=N; i++)
        for(int j=0; j<=i; j++)
            comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % 10007;
    cout << comb[N][K];
}

 

i C j = i-1 C j-1 + i-1 C j임을 활용하여 DP로 풀어주면 됩니다.

 

 

 

 

9375번 : 패션왕 신해빈

 

간단한 조합 문제이지만 문자열을 처리하는 부분이 까다로울 수 있습니다.

각 부위에 대해 N개의 종류의 의상이 있다고 할 때, 입지 않는 경우까지 하여 N+1가지의 선택지가 있습니다.

N+1들의 곱에서 아무것도 입지 않은 상태인 1가지를 빼주면 답이 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;
    while(T--) {
        int N; cin >> N;
        map<string, int> cloth;
        for(int i=0; i<N; i++) {
            string name, type; cin >> name >> type;
            cloth[type]++;
        }

        int ans = 1;
        for(auto i=cloth.begin(); i!=cloth.end(); i++)
            ans *= i->second + 1;
        cout << ans - 1 << "\n";
    }
}

 

위와 같이 map을 활용하여 각 부위의 종류를 번호로 매칭해주고, 해당 배열의 값을 증가시킴으로써 의상의 수를 기록합니다.

iterator를 활용하여 map에 접근하여 값을 받아온 뒤 N+1을 곱해주고, 마지막에 1을 빼주면 됩니다.

 

 

 

 

2004번 : 조합 0의 개수

 

N Combination M이 10의 몇 제곱을 약수로 가지는지를 구하는 문제입니다.

N C M = N! / (N-M)!M! 이므로 N, N-M, M 이하의 수들 중 2와 5를 소인수로 몇 개 가지고 있는지를 구해서 2와 5 중 작은 것을 구해주면 됩니다. (10의 수를 세어야 하기 때문)

 

#include <bits/stdc++.h>
using namespace std;

int cnt(int N, int div) {
    int ret = 0;
    while(div <= N) {
        ret += N/div;
        N /= div;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;
    int two = cnt(N, 2) - cnt(N-M, 2) - cnt(M, 2);
    int five = cnt(N, 5) - cnt(N-M, 5) - cnt(M, 5);

    if(two < five) cout << two;
    else cout << five;
}

 

이를 풀이 코드로 작성해보면 위와 같이 됩니다.

cnt 함수는 N!이 div를 몇 개를 소인수로 가지고 있는지 구하는 함수입니다.

N/div + N/(div*div) + ... 만큼을 소인수로 가지고 있으므로 이를 반복문을 이용해서 구해주면 됩니다.