ACMICPC 2407 조합

문제

nCm을 출력한다.

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

출력

nCm을 출력한다.

문제 한 번 간단해서 좋다!

참 쉬운 문제다 싶어서 시작했는데, 연등 한 번 끝나도록 못 풀고 다음날에야

풀 수 있었다.

컴비네이션의 정의에 따라 nCm = n!/{m!*(n-m)!} 에서 팩토리얼 부분이 문제였다.

n,m의 범위가 100까지다 보니 100! 하면 숫자가 너무 커져 파이썬 마저

부동소수점 문제로 값에 오차가 생겨버렸다.

처음에는 math의 factorial 함수를 사용해서 안되길래,

팩토리얼 함수를 구현해서도 짜봤다.

이역시 값이 커지는건 매한가지니 틀리는게 당연지사...

from math import factorial def combination (n, m): result = 1; for i in range (m): result *= n; n -= 1; for i in range (m): result /= m; m -= 1; return result; n,m = [int(x) for x in input().split()]; result = combination(n, m); print (result); result = factorial(n)/(factorial(m)*factorial(n-m)); print (result); # 100 12 부터 오류 남... # 부동소수점 문제 # 1. 소인수분해? 2. 파스칼의 삼각형 #소인수분해!

생각난 방법이 '소인수분해' 였다.

곱하는 수들을 전부 소인수분해시켜서 답을 소수들의 곱으로 나타내면 되지않을까?

하고 코드를 짜봤다.

다른 방법은 파스칼의 삼각형이 컴비네이션을 나타내니(그림참조) 파스칼의 삼각형을 구현해내서

문제를 푸는 방법도 있긴한데, 음....생략!

소인수분해를 위해 100까지의 소수들을 먼저 찾아주고, 소인수분해하는 함수를 구현해서 풀었다.

문제 풀며 항상 느끼는건데, 어렸을때 수학공부할 때부터 코딩에 관심을 가지고 문제들을 풀었다면

지금보단 훨씬 나은 실력을 가지지 않았을까...싶다. 군대와서 이게 뭐하는 짓인지ㅠㅠ

#2407 조합 n,m = [int(x) for x in input().split()]; def findPrime(n):#소수찾기 함수 for num in range(2, int(n)): isPrime = True; for prime in primeNum: if (num % prime == 0): isPrime = False; break; if isPrime: primeNum.append(num); return primeNum; def intFactorization(n, factor):#소인수분해 함수 for i in range(len(primeNum)): while (n%primeNum[i] == 0): factor[i] += 1; n = n/primeNum[i]; primeNum = []; primeNum = findPrime(100); factor_N = [0 for i in range(len(primeNum))]; factor_M = [0 for i in range(len(primeNum))]; factor_NM = [0 for i in range(len(primeNum))]; result = 1; for i in range(n, 1, -1): intFactorization(i, factor_N); for i in range(m, 1, -1): intFactorization(i, factor_M); for i in range(n-m, 1, -1): intFactorization(i, factor_NM) for i in range(len(primeNum)): factor = factor_N[i] - factor_M[i] - factor_NM[i]; result *= primeNum[i]**factor; print (result);