말 그대로 정수와 조합과 관련된 문제들의 모음이다. 정수론에서는 배수와 약수, 최대공약수, 최소공배수의 개념을 알고 있어야 하며 개념만 잘 이해하고 있다면 이를 코드로 만드는 것은 어렵지 않다. 조합론에서는 조합 즉 이항 계수에 대한 문제를 푼다. 이항 계수를 풀기 위해서 꼭 알고 있어야 할 개념인 팩토리얼과 이항 계수의 정의에 대해서 알고 있다면 정수론과 마찬가지로 어렵지 않다.
추가로 중고등 시절에 수학 공부를 열심히 했다면 문제를 더더욱 쉽게 풀 수 있을 것이다.
1. 5086번 배수와 약수
문제 4 × 3 = 12이다. 이 식을 통해 다음과 같은 사실을 알 수 있다. 3은 12의 약수이고, 12는 3의 배수이다. 4도 12의 약수이고, 12는 4의 배수이다. 두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오. 첫 번째 숫자가 두 번째 숫자의 약수이다.첫 번째 숫자가 두 번째 숫자의 배수이다. 첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다.
입력받은 두 숫자에 대해서 두 수의 관계를 맞추는 문제이다. % 연산을 통해 서로가 서로의 배수인지 약수인지 아무 관계도 아닌지 확인할 수 있다.
#5086번 배수와 약수
while True :
a,b = map(int,(input().split()))
if a == 0 and b == 0 :
break
if a == 0 or b == 0 :
print('neither')
elif b % a == 0 :
print('factor')
elif a % b == 0 :
print('multiple')
else :
print('neither')
2. 1037번 약수
문제 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.
어떤 수 N에 대해서 N의 모든 약수를 1,a1,a2,a3,a4....an,N이라고 하자. 이때 약수는 다음과 같은 규칙을 보인다.
1 x N = a1 x an
즉 N의 진짜 약수들이 주어지면 첫 번째 진짜 약수와 마지막 진짜 약수를 곱해서 어떤 수 N을 구할 수 있다.
그러나 a1~an이 하나만 존재하는 경우가 존재한다. 예를 들어 N이 25일 때 25의 약수는 1,5,25로 진짜 약수가 5 하나뿐이다. 이 때는 하나뿐인 진짜 약수를 제곱해서 어떤 수 N을 구할 수 있다.
#1037번 약수
n = int(input())
factor = sorted(list(map(int,input().split())))
if len(factor) == 1 :
print(factor[0]*factor[0])
else :
print(factor[0]*factor[len(factor)-1])
3. 2609번 최대공약수와 최소공배수
문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
최대공약수를 구하는 효율적이고 유명한 알고리즘으로 유클리드 호제법이 존재한다. 그러나 이번 문제에서는 시간적인 제약이 충분하기 때문에 유클리드 호제법 말고 최대공약수의 정의대로 구해보았다.
소인수분해를 통해 두 수의 소인수를 구한다. 그 다음 중복되는 소인수가 있을 때마다 최대공약수에 곱해준다. 이때 이미 곱한 소인수는 다시 곱하지 않기 위해 이미 곱한 소인수라면 0으로 초기화한다.
최대공약수를 구했다면 최소공배수도 정의대로 구해준다. 두 수 a,b가 존재한다면 a를 최대공약수로 나눈 다음 나눈 값을 b에 곱해준다.
#2609번 최대공약수와 최소공배수
a,b = map(int,input().split())
def factors(n) : #소인수분해
factor = []
while n != 1:
for i in range(2,n+1) :
if n % i == 0 :
n = n//i
factor.append(i)
break
return factor
a_factor = factors(a)
b_factor = factors(b)
max_factor = 1
for i in range(len(a_factor)) :
for j in range(len(b_factor)) :
if a_factor[i] == b_factor[j] :
max_factor *= a_factor[i]
a_factor[i] = 0
b_factor[j] = 0
print(max_factor)
min_multi = b * (a//max_factor)
print(min_multi)
4. 1934번 최소공배수
문제 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다. 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.
이번에는 유클리드 호제법으로 최대공약수를 구해보자. 유클리드 호제법이란 최대공약수를 구하는 알고리즘으로 최대공약수를 정의대로 구하는 것보다 훨씬 효율적으로 구할 수 있다. 숫자 a, b가 있다. a를 b로 나눈 나머지를 a'라고 할 때 a'를 다시 b에 나눈다. 이때 나머지를 b'라고 할 때 b'를 다시 b로 나누고 나머지를 구한다. 나머지가 0이 될 때까지 반복한다. 나머지가 0일 때의 몫이 a, b의 최대공약수이다. 유클리드 호제법은 재귀 함수를 통해 쉽게 만들 수 있다.
유클리드 호제법을 통해 최대공약수를 구한 뒤, 최대공약수를 통해 정의대로 최소공배수를 구한다.
#1934번 최소공배수
n = int(input())
def euclidean(a,b) :
if b == 0 :
return a
else :
return euclidean(b,a%b)
for i in range(n) :
a,b = map(int,input().split())
max_factor = euclidean(a,b)
min_multi = b * (a//max_factor)
print(min_multi)
5. 2981번 검문
문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.
M으로 나누었을 때 나머지가 같게 되는 모든 M을 구한다. 즉 모든 수는 어떤 수 a와 상수 b가 있다고 존재할 때 aM+b이다. 모든 수 중 두 수를 뽑고 이 두 상수를 각각 aM+b, a'M+b라고 해보자. 두 수의 차를 구하면 (a-a') M이 된다. (a-a')은 상수이다. 이때 M에 올 수 있는 것은 M의 모든 약수이다. M = m x M'라고 했을 때 m과 M' 모두 M이 될 수 있다. 즉 모든 수에 대해서 양 옆수와의 차를 구하고 모든 차 룰 구한 수에 대해서 최대공약수를 구하면 최대공약수의 모든 약수가 M이 될 수 있다.
최대공약수는 4번에서 사용한 유클리드 호제법 함수를 그대로 사용해 구한다. 반복문을 통해 붙어있는 항끼리 차를 구하고 두 수의 최대공약수를 구하는 것을 반복한다.
#2981번 검문
n = int(input())
num = []
for i in range(n) :
num.append(int(input()))
def euclidean(a,b) :
if b == 0 :
return a
else :
return euclidean(b,a%b)
num = sorted(num)
max_factor = num[1]-num[0] # 붙어 있는 항끼리 차를 구하고
for i in range(1,n-1) :
max_factor = euclidean(num[i+1]-num[i],max_factor) # 모든 차에 대한 최대공약수를 구한다.
m = [max_factor]
for i in range(2,int(max_factor**0.5)+1) :
if max_factor%i == 0 :
m.append(i)
if i != max_factor//i:
m.append(max_factor//i)
m = sorted(m)
for i in m :
print(i,end=' ')
6. 3036번 링
문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다. 링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.
반지름이 12인 링과 4인 링이 붙어있다고 생각해보자. 맞닿아 있기 때문에 몇바퀴를 돌든 돌아가는 원의 둘레의 길이는 같아야 한다. 이때 원의 둘레는 반지름에 비례한다. 즉 반지름이 12인 링이 한 바퀴 돌았다면 4인 링은 세 바퀴 돌아야 한다.
문제는 시각적으로 기약 분수 형태로 출력해야한다. 어떤 분수에 대해서 기약 분수로 나타내려면 분모와 분자를 최대공약수로 각각 나눠줘야 한다. 유클리드 호제법을 통해 최대공약수를 구하고 각각을 나눠서 출력한다.
#3036번 링
n = int(input())
ring = []
ring = list(map(int,input().split()))
def euclidean(a,b) :
if b == 0 :
return a
else :
return euclidean(b,a%b)
for i in range(1,n) :
temp = euclidean(ring[0],ring[i]) # 첫 번째 수와 i번 째수의 최대공약수
print("%d/%d"%(ring[0]//temp,ring[i]//temp)) # 각 수를 최대공약수로 나눈 값으로 분수를 출력
7. 11050번 이항 계수1
문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 N C K를 구하는 프로그램을 작성하시오.
어떤 수 n, k에 대해서 nCk = n!/k!(n-k)!이다. 재귀 함수를 통해 팩토리얼을 구현하고 팩토리얼을 통해 이항 계수를 계산한다.
#11050번 이항계수 1
n,k = map(int,input().split())
def fact(n) : # 팩토리얼을 통해 이항계수를 구한다
if n > 0 :
return n*fact(n-1)
else :
return 1
print(fact(n)//(fact(k)*fact(n-k))) # 이항계수 공식
8. 11051번 이항 계수 2
문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 N C K를 10007로 나눈 나머지를 구하는 프로그램을 작성하시오.
7번과 다른 점은 N과 K의 범위이다. 7번에 비해 범위가 커졌기 때문에 7번처럼 재귀 함수를 통해 문제를 해결하려고 하면 재귀의 깊이가 너무 깊어 컴파일에 실패한다. 이번에는 재귀 함수가 아닌 반복문을 통해 문제를 해결해보자.
어떤 수 n, k에 대해서 nCk = n!/k!(n-k)! = n*(n-1)*...*(n-k-1)/k!이다. 분모는 n부터 분자는 k부터 k만큼 1씩 감소하며 곱해진다. 반복문을 k만큼 돌려서 이항 계수를 계산할 수 있다.
#11051번 이항계수 2
n,k = map(int,input().split())
N=n
K=k
if k == 0 :
print(1)
else :
while k != 1 : # 이항 계수 공식
n -= 1
N = N*n
k -= 1
K = K*k
print((N//K)%10007)
9. 1010번 다리 놓기
문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.
뭔가 복잡해 보이지만 조금만 생각해보면 간단한 문제이다. 동쪽에는 M개의 사이트가 있고 서쪽에는 N개의 사이트가 있다. 다리를 겹치지 않게 뽑으라고 했지만 동쪽에서 어떤 사이트를 뽑든 간에 일단 뽑고 겹치지 않게 서쪽 사이트와 연결하면 그만이다. 즉 M개의 사이트 중 N개의 사이트를 뽑으면 된다. 이항 계수 M C N이다.
#1010번 다리놓기
t = int(input())
for i in range(t) :
n,m = map(int,input().split())
N=n
M=m
while n!=1:
n-=1
N *= n
m-=1
M *= m
print(M//N)
10. 9375번 패션왕 신해빈
문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경 대신 렌즈를 착용하거나 해야 한다. 해빈이가 가진 의상들이 주어졌을 때 과연 해빈이는 알몸이 아닌 상태로 며칠 동안 밖에 돌아다닐 수 있을까?
옷의 종류와 옷의 이름을 입력받는다. 사실 옷의 이름은 중요하지 않기 때문에 종류별로 카운팅만 잘하면 된다. 그다음 각 옷들로 조합할 수 있는 모든 경우의 수를 구해야 한다. 고등학교 시절 수학 공부를 열심히 했으면 바로 떠오르는 공식이 있을 것이다. 두 집합 A, B가 있을 때 A의 원소 개수를 a개, B의 원소 개수를 b 개라고 한다면 두 집합의 원소들로 만들 수 있는 모든 부분집합의 개수는 (a+1) x (b+1)이다. 이 공식을 10번 문제에 적용할 수 있다. 각 옷(집합)마다 옷의 개수가 있고 이 옷들로 조합할 수 있는 모든 경우의 수(부분집합)를 구한다. 모자가 3개 있고 상의가 2개, 하의가 4개라면 옷을 입을 수 있는 모든 경우의 수는 4x3x5이다. 이때 옷을 하나도 안 입는 경우는 카운팅 하지 않으므로 1을 빼준다.
#9375번 패션왕 신해빈
from itertools import combinations
t = int(input())
for i in range(t) : # 모든 테스트 케이스에 대해
n = int(input())
cloth = []
for j in range(n) : # 모든 옷, 종류에 대해
name,kind = input().split()
check = 0 # 이미 존재하는 종류인지 여부
for l in range(len(cloth)) :
if cloth[l][0] == kind : # 이미 존재하는 종류의 옷이라면
cloth[l][1] += 1 # 종류 하나 추가
check = 1 # 이미 존재하는 옷이라고 표시
if check == 0 : # 새로운 종류의 옷이라면
cloth.append([kind,1]) # 종류 추가
result = 1
for j in range(len(cloth)) :
result *= (cloth[j][1]+1) # 모든 종류의 옷의 개수 +1만큼 전부 곱한 후
print(result-1) # 아무것도 안입는 경우 1 빼고
11. 1676번 팩토리얼 0의 개수
문제 N! 에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
뒤에 0이 나온다는 것은 반드시 10의 배수임을 나타낸다. 10을 만들기 위해서는 5와 2를 곱해야 된다. 즉 이 문제는 N! 의 소인수 중 5와 2의 개수를 찾는 것이다. 단 2가 5보다 훨씬 많기 때문에 5의 개수만 찾으면 된다.
N! 을 나열하면 Nx(N-1) x(N-2)... 3x2x1이다. 각 수들의 소인수에 5가 몇 개인지 확인한다. 125의 배수라면 카운팅을 세 번, 125의 배수가 아니면서 25의 배수라면 카운팅을 두 번, 25의 배수가 아니면서 5의 배수라면 카운팅을 한 번 해준다. 단 이 방법은 N의 범위가 비교적 작기 때문에 가능하다.
#1676번 팩토리얼 0의 개수
n = int(input())
result = 0
for i in range(5,n+1,5) :
if i%125 == 0 :
result += 3
elif i%25 == 0 :
result += 2
elif i%5 == 0 :
result += 1
print(result)
12. 2004번 조합 0의 개수
문제 nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.
11번 문제의 연장선이라고 할 수 있다. 11번에서는 팩토리얼이었지만 이번에는 조합이다. 11번에서는 5보다 2가 무조건 많기 때문에 5의 개수만 확인했지만 조합의 경우 2가 더 적은 경우도 있기 때문에 이번에는 5와 2의 개수 모두 확인해줘야 한다.
또한 이번에는 시간 초과의 제약이 11번보다 강하다. 11번에서는 팩토리얼에 존재하는 모든 수를 검사했지만 이번에는 좀 더 효율적인 방법이 필요하다. 26! 에서 5의 개수를 구한다고 가정해보자. 1부터 26까지 모든 수를 곱한다. 1부터 26사에는 25의 배수가 한 개, 5의 배수는 5개 있다. 숫자 25는 25의 배수로 한 번, 5의 배수로 한 번 총 두 번 카운팅 된다. 이는 26을 25로 나눴을 때와 5로 나눴을 때의 몫과 같다. 즉 N! 에 대해서 5가 몇번 곱해지는지 구하려면 N을 5의 제곱들(5,25,125...)로 나눈 몫을 전부 더하면 된다. 이를 더 일반화해서 N!에 대해서 k가 몇 번 곱해지는지 구하려면 N을 k의 제곱들로 나눈 몫을 전부 더하면 된다.
nCm을 구할 때 세 개의 팩토리얼이 존재한다. n!, m!, (n-m)!이다. 각 팩토리얼에서 위의 공식을 통해 곱해지는 5와 2의 개수를 전부 구한다. nCm = n!/m!(n-m)! 이므로 중복되는 중복되는 5와 2의 개수만큼 사라진다. n! 에서 구한 5와 2의 개수에서 m! 와 (n-m)! 에서 구한 5와 2의 개수를 뺀다. 이렇게 구한 5와 2가 nCm의 소인수로 존재하는 5와 2의 개수이다.
최종적으로 nCm의 소인수로 존재하는 5와 2를 구했다. 5와 2 둘 다 있어야 10이 만들어지기 때문에 둘 중 더 개수가 적은 수를 출력한다.
#2004번 조합 0의 개수
n,m = map(int,input().split())
n_5 = 0
m_5 = 0
n_m_5 = 0
n_2 = 0
m_2 = 0
n_m_2 = 0
# n!의 5의 개수
i = 1
while n >= 5**i :
n_5 += n // 5**i
i += 1
# m!의 5의 개수
i = 1
while m >= 5**i :
m_5 += m // 5**i
i += 1
# (n-m)!의 5의 개수
i = 1
while (n-m) >= 5**i :
n_m_5 += (n-m) // 5**i
i += 1
# n!의 2의 개수
i = 1
while n >= 2**i :
n_2 += n // 2**i
i += 1
# m!의 2의 개수
i = 1
while m >= 2**i :
m_2 += m // 2**i
i += 1
# (n-m)!의 2의 개수
i = 1
while (n-m) >= 2**i :
n_m_2 += (n-m) // 2**i
i += 1
five = n_5 - m_5 - n_m_5 # nCm 의 5의 개수
two = n_2 - m_2 - n_m_2 # nCm 의 2의 개수
print(min(two,five)) # 둘 중 더 작은거 출력
