# [TIL] Algorithms Day 5 - Greedy, Combination

# Problem 1. [Coin](https://www.acmicpc.net/problem/11047) (Greedy)

```python
N, K = map(int, input().split())
arr = []
count = 0
for _ in range(N):
    arr.append(int(input()))


for i in range(N-1, -1, -1):
    if K >= arr[i]:
        count += K // arr[i]
        K = K % arr[i]
print(count)
```

# Problem 2. [Binomial Coefficient](https://www.acmicpc.net/problem/11050) (Combination)

* Binomial Coefficient: A binomial coefficient C(n, k) also gives the number of ways, disregarding order, that k objects can be chosen from among n objects more formally, the number of k-element subsets (or k-combinations) of a n-element set.
    
* Combination Formula: nCk = nCn-k = n!/(k!(n-k)!)
    

```python
n, k = map(int, input().split())

def factorial(n):
    answer = 1
    for i in range(1, n+1):
        answer *= i
    return answer

# if the recursive function is used, we need to set the recursion depth to avoid RecursionError (set the boundary for the call stack)

# def factorial_recursion(n):
#     if n == 1:
#         return 1
#     return n * factorial_recursion(n-1)

print(factorial(n)//(factorial(k)*(factorial(n-k))))
```

```python
import itertools

n, k = map(int, input().split())

arr = [i for i in range(n)]
print(len(list(itertools.combinations(arr, k))))
```

# Problem 3. [Missing Parenthesis](https://www.acmicpc.net/problem/1541) (Greedy)

```python
sik = input()

result=sik.split('-')

fin=sum(list(map(int, result[0].split('+'))))

for i in range(1,len(result)): 
    fin -= sum(list(map(int, result[i].split('+'))))

print(fin)
```

# Useful Methods in Python

* [itertools](https://www.geeksforgeeks.org/permutation-and-combination-in-python/)
    
    * `itertools.combination()`
        
    * `itertools.permutations()`
        
* collections
    
    * [`collections.Counter`](https://www.geeksforgeeks.org/python-counter-objects-elements/)`(list)`
        
        * `Counter(list).`[`most_common`](https://pythontic.com/containers/counter/most_common)`([limit])`
            
    * [`collections.defaultdict`](https://www.geeksforgeeks.org/defaultdict-in-python/)`(function to return default value for key with no value specified)`
        
    * [`collections.OrderedDict`](https://www.geeksforgeeks.org/ordereddict-in-python/)`()` : preserves the order in the dictionary object
        
* [`enumerate`](https://www.geeksforgeeks.org/ordereddict-in-python/)`()` : keep a count of iterations