행복한 개구리

T = int(input()) items = {} for i in range(T): nums = int(input()) for j in range(nums): name, category = map(str, input().split()) val = [] if category in items.keys(): items[category].append(name) else: items[category] = [name] result = 1 for k in items: v = items[k] result *= len(v)+1 print(int(result)-1) items.clear() factorial을 이용한 조합으로 풀어보려했으나 오답처리가 되어 다시 작성했습니다. dictionary를 사용한 코드입니다. 입력받..

T = int(input()) dp = [[1] for i in range(31)] for i in range(1, 31): for j in range(i+1): if j == 0: dp[i][j] == 1 elif j == i: dp[i].append(1) else: dp[i].append(dp[i-1][j-1]+dp[i-1][j]) for _ in range(T): a, b = map(int, input().split()) if a < b: a, b = b, a print(dp[a][b]) 결국 서쪽 다리와 동쪽 다리의 조합을 구하는 문제입니다. 그리고 출처에 다이나믹 프로그래밍이 포함되어 있길래 dp를 이용해보았습니다. dp를 이용하여 파스칼의 삼각형을 만들겁니다. 이항의 0제곱일 때는 이항계수가 ..

from math import factorial N, K = map(int, input().split()) print((factorial(N)//(factorial(K)*factorial(N-K))) % 10007) 이항계수를 구하여 바로 10007로 나누어줘도 정답처리가 됩니다. 하지만 문제 아랫쪽 알고리즘 분류에 다이나믹 프로그래밍이 있으니 dp를 사용해봅시다. N, K = map(int, input().split()) dp = [[0]for i in range(N+2)] dp[1].append(1) for i in range(2, N+2): for j in range(1, i+1): if j == 1: dp[i].append(1) elif j == i: dp[i].append(1) else: dp[..

이항 정리 - 위키백과, 우리 모두의 백과사전 초등대수학에서, 이항 정리(二項定理, 문화어: 두마디공식, 영어: binomial theorem)는 이항식의 거듭제곱을 이항 계수를 계수로 하는 일련의 단항식들의 합으로 전개하는 정리이다. 이항 정리를 사 ko.wikipedia.org 이항정리, 이항계수를 알아봅시다. 수학시간에 방정식이라는 것을 배워본 적이 있을겁니다. 그 중 두 항을 더하는 식의 제곱을 구하는 공식은 (a+b)² = a² + 2ab + b² 이며 두 항을 더하는 식의 세제곱을 구하는 공식은 (a+b)³ = a³ + 3a²b + 3ab² + b³ 입니다. 하지만 (a+b)ⁿ = xaⁿ⁻¹b + yaⁿ⁻²b² + … + bⁿ 처럼 n제곱을 구하는 식에서의 결괏값의 각 항의 계수는 구하는 공식..

유클리드 호제법 - 위키백과, 우리 모두의 백과사전 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 ko.wikipedia.org 유클리드 호제법은 최대공약수를 구할 때 사용되는 방법이며 큰 수(A)를 작은 수(B)로 나누어 그 나머지를 이용하여 최대공약수를 구하는 방법입니다 이 문제를 풀기위해 방정식으로 정리를 해보았습니다 A, B 두개의 수가 같은 나머지 값을 갖도록 하는 수를 구하려면 방정식은 다음과 같습니다 d = 최대공약수, r = 나머지입니다 A = a * d + r, B = b * d + r 이것을 계산해보면 (A - B) = (..

유클리드 호제법 - 위키백과, 우리 모두의 백과사전 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 ko.wikipedia.org 유클리드 호제법은 최대공약수를 구할 때 사용되는 방법이며 큰 수(A)를 작은 수(B)로 나누어 그 나머지를 이용하여 최대공약수를 구하는 방법입니다 def gcd(a, b): if a < b: a, b = b, a if b == 0: return a if a % b == 0: return b else: return gcd(b, a % b) T = int(input()) for i in range(T): A, B = ..