[코테 준비 : day13]

영-차! 좋아쒀!

1. 부분수열의 합
   https://www.acmicpc.net/problem/1182
   
   combinations으로 조합들을 만든 후 합이 S와 같은 것을 찾으면 끝!

from itertools import combinations
answer=0
n,s=map(int,input().split())
num=list(map(int, input().split()))
for i in range(1,n+1):
    for j in combinations(num, i):
        if sum(j)==s:
            answer+=1
print(answer)

2. 로또
   https://www.acmicpc.net/problem/6603
   
   이것 또한 combinations..! easy!

from itertools import combinations
while True:
    num=list(map(int,input().split()))
    k=num[0]
    num=num[1:]
    re=[]
    for i in combinations(num,6):
        re.append(i)
    for j in sorted(re):
        print(*j)
    if k ==0:
        exit()
    print()

3. N과M (2)
   https://www.acmicpc.net/problem/15650
   
   또 combinations..? yes

from itertools import combinations

N, M = map(int, input().split())

numList = [i for i in range(1, N+1)]
for seq in combinations(numList, M):
    print(*seq)

4. 최대 공약수
   https://www.acmicpc.net/problem/2824
   

math 라이브러리에서 내장함수를 사용하면 코드가 정말 간단하다!

import math 

a = int(input())
b = map(int,input().split())
N = math.prod(b) 

c = int(input())
d = map(int,input().split())
M = math.prod(d)

print((str(math.gcd(N,M))[-9:]))

5. 검문
   https://www.acmicpc.net/problem/2981
   

n = int(input())
nums = [int(input()) for i in range(n)]
nums.sort()

def gcd(x,y):
    if x%y == 0:
        return y
    return gcd(y,x % y)
    # 최대공약수 함수

a = []
for i in range(1,n):
    a.append(nums[i] - nums[i-1])
a.sort()
# 숫자들의 차를 담은 배열

while(len(a)!=1):
    for i in range(1,len(a)):
        a[i-1] = gcd(a[i],a[i-1])
    a = a[:len(a)-1]
a = a[0]
# 숫자가 하나가 남을 때까지 최대공약수를 구함

result = [a]
for i in range(2,int(a**0.5)+1):
    if a%i == 0:
        result.append(i)
        result.append(a//i)
print(*sorted(list(set(result))))
# 하나 남은 최대공약수의 약수들을 구함