조합론 10

백준(Python) 17471번 게리맨더링 풀이

Python으로 구현한 17471번 게리맨더링 문제 풀이입니다. https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net from collections import defaultdict, deque def combinations(arr, r) : for i in range(len(arr)) : if r == 1 : yield [arr[i]] else : for next in combinations(arr[i+1:], r-1) : yield [arr[i]] + next def..

백준(JAVA) 6603번 로또 풀이

Java으로 구현한 6603번 로또 문제 풀이입니다. https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net import java.util.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); while (true) { int k = sc.nextInt(); if (k == 0) bre..

백준(Python) 6603번 로또 풀이

Python으로 구현한 6603번 로또 문제 풀이입니다. https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net from itertools import combinations while True : try : data = list(map(int, input().split())) if data[0] == 0 and len(data) == 1 : break del data[0] result = [] for combi in combinations..

백준(Python) 16395번 파스칼의 삼각형 풀이

Python으로 구현한 16395번 파스칼의 삼각형 문제 풀이입니다. https://www.acmicpc.net/problem/16395 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net data = [[1 for _ in range(i)] for i in range(1, 31)] for i in range(2, 30) : for j in range(1, i) : data[i][j] = data[i-1][j-1] + data[i-1][j] n, k = map(int, input().split()) p..

백준(Python) 15439번 Vera and Outfits 풀이

Python으로 구현한 15439번 Vera and Outfits 문제 풀이입니다. https://www.acmicpc.net/problem/15439 15439번: Vera and Outfits Vera owns N tops and N pants. The i-th top and i-th pants have colour i, for 1 ≤ i ≤ N, where all N colours are different from each other. An outfit consists of one top and one pants. Vera likes outfits where the top and pants are not the same colour. www.acmicpc.net n = int(input()) pri..

백준(Python) 2407번 조합 풀이

Python으로 구현한 2407번 조합 문제 풀이입니다. https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net n, m = map(int, input().split()) value = 1 value2 = 1 for i in range(n, n-m, -1) : value *= i for i in range(2, m + 1) : value2 *= i print(value // value2) 문제에서 요구한 바와 같이 nCm 을 구하여 출력한다. 첫번째 반복문은 n부터 n-m 전까지 곱한 코드이며, 두번째 반복문은 2부터 m 까지 곱한 코드이다. 최종적으로 value를 ..

백준(Python) 11051번 이항 계수2 풀이

Python으로 구현한 11051번 이항 계수 2 문제 풀이입니다. https://www.acmicpc.net/problem/1009 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net def factorial(x) : result = 1 for i in range(2, x + 1) : result *= i return result n, k = map(int, input().split()) value = factorial(n) // (factorial(n-k) * factorial(k)) print(value % 10007..

백준(Python) 11050번 이항 계수 1 풀이

Python으로 구현한 11050번 이항 계수 1 문제 풀이입니다. https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net def factorial(x) : value = 1 for i in range(2, x+1) : value *= i return value n, k = map(int, input().split()) result = factorial(n) // (factorial(n-k) * factorial(k)) print(result) 이 문제에서 요구하는 이항 계수를 해결하는 공식은 아래와 같다. 그러므로, fact..

백준(Python) 1010번 다리 놓기 풀이

Python으로 구현한 1010번 다리 놓기 문제 풀이입니다. https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net tc = int(input()) def factorial(x) : count = 1 for i in range(2, x + 1) : count *= i return count for _ in range(tc) : a, b = map(int, input().split()) result = factorial(b) // (factorial(..

백준(C) 11050번 이항 계수 1 풀이

C로 구현한 11050번 이항 계수 1 문제 풀이입니다. https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net #include int main() { int n, k, a1 = 1, a2 = 1, b = 1; scanf("%d %d", &n, &k); for(int i=n-k; i>=2; i--) { a1 *= i; } for(int i=k; i>=2; i--) { a2 *= i; } for(int i=n; i>=2; i--) { b *= i; } printf("%d\n", b/(a1*a2)); } 이 문제에서 요구하는 이항..