오늘의 코딩#27

오늘은 백준에서 지난번에 풀던 정수론 및 조합론 단계의 문제를 이어서 풀었다.

어제도 풀기는 했는데 생략 했었는데 오늘까지 풀어서 이제 12문제 중에서 2문제 남았다.

오늘 푼 문제는 이항 계수 2, 다리 놓, 패션왕 신해빈, 팩토리얼 0의 개수 문제를 풀었다.

정수 N 과 K 를 입력받아 이항 계수 (N K)를 구하는 문제인데 이전 문제와 달리 매우 큰 수에 대해서도 가능해야 해서 그 값을 10007로 나눈 나머지를 구하는 문제이다.

1000까지 가능 하기 때문에 일반적인 조합식으로는 값을 구할 수 없어서 이항 정리를 이용해 동적 계획법으로 풀었다.

#include <stdio.h>

int binomial_theorem(int n, int k, int dp[][1001])
{
if (dp[n][k])
return (dp[n][k]);
else if (n == k)
dp[n][k] = 1;
else if (k >= 1)
dp[n][k] = binomial_theorem(n - 1, k, dp) + binomial_theorem(n - 1, k - 1, dp);
else
dp[n][k] = 1;
dp[n][k] %= 10007;
return (dp[n][k]);
}

int main(void)
{
int n, k;
int dp[1001][1001] = {0,};

scanf("%d %d", &n, &k);
printf("%d\n", binomial_theorem(n, k, dp));
return (0);

}

함수 자체는 상당히 쉬운데 이걸 생각해 내는게 어려웠다.

다리 놓기 문제는 그냥 이걸 활용하는 k개의 지점에서 n개의 지점으로 연결하는 다리를 놓는 방법을 찾는 문제인데 사실상 위의 문제를 활용하는 문제라 생략하겠다.

패션왕 신해빈 문제는 같은 조합으로 옷을 입지 않는 해빈에게 옷을 입히는 모든 방법을 찾는 문제이다.

이때 해빈이는 아무 옷도 입지 않는 경우는 없으며 같은 용도의 옷을 동시 입을 수는 없다.

예를 들어
hat headgear
sunglasses eyewear
turban headgear
이런 식으로 입력 받으면 headgear 인 hat, turban 과 eyewear 인 sunglasses 가 있는 데 이를 조합하는 모든 경우의 수는 5 이므로 5를 출력하는 문제이다.

이 문제의 경우 딕셔너리 자료형을 이용하면 매우 쉬워지기 때문에 오랜만에 파이썬으로 코드를 짰다.

import sys
t = int(input())

for t1 in range(t):
n = int(input())
dic = {}
for t2 in range(n):
i1, i2 = sys.stdin.readline().strip().split()
if i2 not in dic:
dic[i2] = []
dic[i2].append(i1)
case = 1
for k in dic.keys():
case *= len(dic[k]) + 1
print(case - 1)

각 용도의 의복 + 1 을 모두 곱한 경우에서 아무것도 입지 않는 경우를 빼면 답이므로 이렇게 구성했다.

그 다음 문제인 팩토리얼 0의 개수는 N!의 뒤에서 0이 아닌 수가 나오기까지 0이 몇개나 있는지 구하는 문제이다.

이 문제는 N!에서 10이 몇개나 있는지 구하면 되므로 그리 어려운 문제는 아니었다.

#include <stdio.h>

void tool(int n, int element[2])
{
while (n % 2 == 0)
{
element[0]++;
n /= 2;
}
while (n % 5 == 0)
{
element[1]++;
n /= 5;
}
}

int main(void)
{
int n, i;
int element[2] = {0,};

scanf("%d", &n);
for (i = 0; i < n; i++)
    tool(i + 1, element);
printf("%d\n", element[0] < element[1] ? element[0] : element[1]);
return (0);

}

2와 5중 더 작은 값이 10의 개수이므로 이렇게 구성했다.

오늘은 오랜만에 파이썬으로 코딩을 했더니 기억이 잘 나지 않았다.

하지만 그래도 확실히 파이썬이 훨씬 쉬운 것 같다.