1. 활동 내역

• 알고리즘 문제 해결 전략 공부 및 문제풀이

1) 알고리즘 문제해결(조합 및 순열)

이 문제는 주어진 조건에 따라 조합과 순열을 계산하는 알고리즘을 구현하는 것이다. 이 알고리즘은 특정 조건을 만족하는 경우의 수를 구하는 데 사용되며, 조합과 순열의 계산을 포함한다.

풀어본 문제: 비밀번호 찾기

#include <stdio.h>
long long comb(int a, int b) {
    if (b > a) return 0;
    if (b * 2 > a) b = a - b;
    if (b == 0) return 1;

    long long res = a;
    for (int i = 2; i <= b; i++) {
        res *= (a - i + 1);
        res /= i;
    }
    return res;
}

long long perm(int a, int b) {
    if (b > a) return 0;
    long long res = 1;
    for (int i = 0; i < b; i++) {
        res *= (a - i);
    }
    return res;
}

int main() {
    int n, m, x, y;
    scanf("%d %d %d %d", &n, &m, &x, &y);

    int setPW = 0;
    int noneSetPW = 0;

    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);

        if (a != 0) {
            setPW++;
        } else {
            noneSetPW++;
        }
    }

    n -= setPW;

    long long result = 1;

    if (noneSetPW > 0) {
        result *= comb(n, noneSetPW) * perm(noneSetPW, noneSetPW);
    }

    n -= noneSetPW;

    if (n > 0) {
        result *= perm(9 - (setPW + noneSetPW), n);
    }

    printf("%lld\\n", result * x + (result - 1) / 3 * y);

    return 0;
}

조합 함수(comb):

• comb 함수는 두 개의 정수 a와 b를 입력으로 받아 a에서 b개를 선택하는 조합의 수를 계산한다.
• b가 a보다 크면 0을 반환하고, b가 a의 절반보다 크면 b를 a - b로 조정하여 계산의 효율성을 높인다.
• b가 0일 경우 1을 반환하며, 반복문을 통해 조합 수를 계산한다.

순열 함수(perm):

• perm 함수는 두 개의 정수 a와 b를 입력으로 받아 a에서 b개를 선택하는 순열의 수를 계산한다.
• b가 a보다 크면 0을 반환하고, 반복문을 통해 순열 수를 계산한다.

메인 함수(main):

• 사용자로부터 n, m, x, y를 입력받고, m개의 쌍을 입력받아 setPW와 noneSetPW를 카운트한다.
• setPW는 설정된 경우의 수를 나타내며, noneSetPW는 설정되지 않은 경우의 수를 나타낸다.
• 설정된 경우 수에 따라 n을 감소시키고, 조합과 순열을 계산하여 최종 결과를 구한다.
• 결과를 출력할 때는 주어진 x와 y를 사용하여 계산한다.