[BOJ] 정수론 및 조합론 / 17단계

자바로만 풀다가 파이썬 공부할겸 이번 단계에서는 파이썬으로만 풀었습니다.

 

 

1	5086	배수와 약수	성공출처다국어분류	7239	10516	70.288%
배수와 약수를 배우는 문제

def test(num01, num02) :
    if num02 % num01 == 0 :
        print("factor")
    elif num01 % num02 == 0:
        print("multiple")
    else :
        print("neither") 
        

while True :
    number01, number02 = map(int, input().split())
    if number02 == 0 and number01==0 :
        break
    test(number01, number02)
    

---

2	1037	약수	성공분류	12488	25527	49.747%
약수의 성질을 활용하는 문제

testNum = int(input())
array = list(map(int,input().split()))
a_max = max(array)
a_min = min(array)
print(a_max * a_min)

---

3	2609	최대공약수와 최소공배수	성공출처분류	23552	39661	62.096%
최대공약수와 최소공배수를 구하는 문제

def firstTest(a,b) :
    if a<b :
        temp = a
        for i in range(a) :
            if b%temp == 0 and a%temp == 0:
                break
            else :
                temp -= 1
    else :
        temp = b
        for i in range(b) :
            if b%temp == 0 and a%temp == 0:
                break
            else :
                temp -= 1
    return temp

def secondTest(a,b,x) :
    print((a//x)*(b//x)*x)


a, b = map(int,input().split())
x=firstTest(a,b)
print(x)
secondTest(a,b,x)

---

4	1934	최소공배수	성공분류	15809	27243	59.910%
유클리드 알고리즘으로 더 빠르게 푸는 문제

def firstTest(a,b) :
    if a<b :
        temp = a
        for i in range(a) :
            if b%temp == 0 and a%temp == 0:
                break
            else :
                temp -= 1
    else :
        temp = b
        for i in range(b) :
            if b%temp == 0 and a%temp == 0:
                break
            else :
                temp -= 1
    return temp

def secondTest(a,b,x) :
    print(a*b//x)

T = int(input())

for i in range(T) :
    a, b = map(int,input().split())
    secondTest(a,b,firstTest(a,b))

---

5	2981	검문	성공출처다국어분류	3473	18733	20.916%
N개의 수를 M으로 나누었을 때, 나머지가 전부 같은 M을 찾는 문제

from math import gcd, sqrt

T = int(input())
array = [input() for i in range(T)]
array= list(map(int, array))
array.sort(reverse=True)

answer = list()
for i in range(1, len(array)) :
  x = array[i] - array[i-1]
  answer += [(gcd(x))]

for i in range(1,len(answer)):
      answer[i] = gcd(answer[i], answer[i-1])

x = int(answer[-1])

a=[]
for i in range(2, int(sqrt(x)) + 1):
    if x % i == 0:
        a.append(i)
        a.append(x // i)
a.append(x)
a = list(set(a))
a.sort()
#a.remove(1)
for i in a:
    print(i, end = ' ')

---

6	3036	링	성공출처다국어분류	5051	6542	79.385%
첫번째 링을 한 바퀴 돌렸을 때, 나머지 링이 몇 바퀴 도는지 구하는 문제

import math
def test(mainNum, subNum) :
    x = math.gcd(mainNum, subNum)
    print("{0}/{1}".format(mainNum//x, subNum//x))

T = int(input())
array = list(map(int, input().split()))
for i in array :
    if i == array[0] : continue
    test(array[0], i)

---

7	11050	이항 계수 1	성공분류	13430	20880	64.841%
N개의 물건 중 순서를 고려하지 않고 K개를 고르는 경우의 수, 이항 계수를 구하는 문제

def fac1(num) :
    if num==1 : return 1
    return num*fac(num-1)

def fac2(num) :
    temp =1
    for i in range(1,num+1) :
        temp *= i
    return temp

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

if K < 0 or K>N :
    print(0)
    
else :
    print(fac2(N) // (fac2(K)*fac2(N-K)))

---

 

8	11051	이항 계수 2	성공분류	10763	28608	38.462%
더 넓은 범위의 이항 계수를 동적 계획법으로 구하는 문제

def fac1(num) :
    if num==1 : return 1
    return num*fac1(num-1)

def fac2(num) :
    temp =1
    for i in range(1,num+1) :
        temp *= i
    return temp

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

if K < 0 or K>N :
    print(0)
    
else :
    print((fac2(N) // (fac2(K)*fac2(N-K)))%10007)

---

9	1010	다리 놓기	성공분류	15752	34705	48.470%
다리를 놓는 경우의 수를 구하는 문제

def fac(num) :
    temp =1
    for i in range(1,num+1) :
        temp *= i
        
    return temp


def fac1(num) :
    if num==1 : return 1
    return num*fac1(num-1)

T = int(input())
for i in range(T) :
    b, a = map(int, input().split())
    x= fac(a-b)*fac(b)
    y = fac(a) 
    print(y//x)

---

10	9375	패션왕 신해빈	성공출처다국어분류	4745	8973	54.356%
경우의 수 연습문제

from collections import Counter
t = int(input())
for i in range(t):
    n = int(input())
    s = []
    for j in range(n):
        a, b = input().split()
        s.append(b)
    num = 1
    result = Counter(s)
    for key in result:
        num *= result[key] + 1
    print(num - 1)
    
##처음에 아래같이 접근했다가 collections 생각나서 다시풀었음
# import math

# T = int(input())
# array = []
# for i in range(T) :
#     x = int(input())
#     for j in range(x) :
#         array[i].append(input().split())

#     array[i].sort(key = lambda x: (x[1]))

#     tempStr = array[i][0][1]
#     count = 1
#     subSum = 0
#     for z in range(len(array[0])) :
#         if z == 0 : continue

#         if array[i][z][1] == tempStr :
#             if z == len(array[0])-1 and count !=1 :
#                 subSum += math.factorial(count)
#                 break
#             else : 
#                 count +=1
#                 continue

#         elif count == 1 :
#             tempStr = array[i][z][1]
#             continue
#         else :
#             subSum += math.factorial(count)
#             count = 1
#             tempStr = array[i][z][1]
#             continue
#     max = math.factorial(len(array[0]))
#     print(max - subSum +1)
        
# ##############################
# # def x :
    
# #     for a,b in array[0] :

# #         if firstPass == 0 : 
# #             firstPass +=1
# #             continue
        
# #         if b == tempStr :
# #             count += 1
# #             firstPass +=1
# #             continue
            
# #         elif count == 1 : 
# #             firstPass +=1
# #             continue
        
# #         else :
# #             subSum += math.factorial(count)
# #             firstPass +=1
# #             count = 1
# #             continue
        
# #         if firstPass == len(array[i])-1:
# #             subSum += math.factorial(count)
# #             break

---

11	1676	팩토리얼 0의 개수	성공분류	11789	24977	47.672%
소인수분해의 성질을 활용하여 N!의 끝에 0이 얼마나 많이 오는지 구하는 문제

x = int(input())
print(x//5 + x//25 + x//125)

---

12	2004	조합 0의 개수	성공분류	6233	22764	28.769%
위와 비슷한데 N! 대신 이항계수가 들어간 문제

import math
def zero(num, x) :
    temp = x
    sum = 0
    while temp<=2000000000 :
        sum += num//temp
        temp *= x
    return sum

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

if K < 0 or K>N :
    print(0)
    
else :
    a = zero(N,5) - zero(K,5) - zero(N-K,5)
    b = zero(N,2) - zero(K,2) - zero(N-K,2)
    print(min(a,b))
    

 

이번 단계는 좀 쉽다고 느껴져서 편하게 Github 잔디 채울 겸 파이썬으로 풀었다.