[백준/python] 정수론 및 조합론 전체 풀이(14단계)

 

목차

 

배수와 약수(#5086)

• Problem

4 × 3 = 12이다. 이 식을 통해 다음과 같은 사실을 알 수 있다. 3은 12의 약수이고, 12는 3의 배수이다. 4도 12의 약수이고, 12는 4의 배수이다. 두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오. 첫 번째 숫자가 두 번째 숫자의 약수이다. 첫 번째 숫자가 두 번째 숫자의 배수이다. 첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다.

 

• Hint

나머지를 이용하여 약수인지 배수인지를 구별하자

• Solution

나머지를 이용한 풀이

a=b=1
res=[]
while a+b!=0:
    a,b=map(int,input().split())
    if a>b and a%b==0:
        res.append('multiple')
    elif a<b and b%a==0:
        res.append('factor')
    else:
        res.append('neither')

print(*res[:-1],sep='\n')

 

---

 

 

약수(#1037)

• Problem

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

 

• Hint

홀수 짝수 일때를 나누어서 생각해보자

• Solution

홀짝을 이용한 풀이

n=int(input())
a=sorted(list(map(int,input().split())))

if n%2==1:
    print(a[int((n-1)/2)]**2)
else:
    print(a[int((n-1)/2)]*a[int((n-1)/2+1)])

---

 

최대공약수와 최소공배수(#2609)

• Problem

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

• Hint

최소공배수와 최대공약수의 특징을 잘 생각해보자

 

시간초과를 피하기 위해서는 loop 를 적게 돌아야한다.

 

• Solution

while 을 이용한 풀이

a,b = map(int,input().split())

di=[]

for i in range(max(a,b)):
    if a%(i+1)==0 and b%(i+1)==0:
        di.append((i+1))

mul=max(a,b)
res=0
i=0

while res==0:
    if (mul*(i+1))%a==0 and (mul*(i+1))%b==0:
        res=mul*(i+1)
    i+=1     

print(max(di))
print(res)

최소공배수를 구할때 시간초과가 일어날 수 있는데 위의 경우에는 두 값중 최대값의 배수만 확인해보았다.

---

 

최소공배수(#1934)

• Problem

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다. 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

 

• Hint

유클리드 호제법을 이용해보자

 

• Solution

유클리드 호제법을 이용한 풀이

import sys
input=sys.stdin.readline

def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

n= int(input())
res=[]
for i in range(n):
    l=sorted(list(map(int,input().split())))
    res.append(int(l[0]*l[1]/gcd(int(l[1]),int(l[0]))))

print(*res,sep='\n')

확실히 알고리즘 공부를 할 때에는 시간 복잡도가 낮은 알고리즘을 외워두어야 하는 것이 필수인것 같다. 

 

최대 공약수를 구할때 min(a,b)부터 1까지 루프를 돌면서 최대공약수를 구하게 했었는데 두 수다 소수이고 그 값이 매우 클때 어김없이 시간초과가 나왔다.

 

---

 

검문(#2981)

• Problem

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

 

• Hint

두가지 스킬을 사용할 줄 알아야한다.

 

• Solution

대수론을 이용한 풀이

import sys
import math
input=sys.stdin.readline

def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

n= int(input())
res=[]
arr=[]
rearr=[]
for i in range(n):
    arr.append(int(input()))
for i in range(n):
    if i==n-1:
        rearr.append(arr[n-1]-arr[0])
    else:
        rearr.append(arr[i+1]-arr[i])    
rearr.sort()
minrearr=rearr[0]
for i in range(n):
    minrearr=gcd(minrearr,rearr[i])

for j in range(math.ceil(minrearr**0.5)):
    if minrearr%(j+1)==0:
        res.append(j+1)
        res.append(int(minrearr/(j+1)))
print(*sorted(set(res))[1:])

이런 문제들은 수의 분해를 통해서 생각해보려고 하는 편이다.

 

자세한 풀이는 이 포스팅에서

 

백준 2981번[검문] :: 약수 구하기

---

 

링(#3036)

• Problem

상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다. 링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.

 

• Hint

기약함수 : 더이상 약분이 되지 않는 함수

• Solution

최대공약수을 이용한 풀이

import sys
input=sys.stdin.readline

def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)

n=int(input())
l=list(map(int,input().split()))

for i in l[1:]:
    divr=gcd(l[0],i)
    print(f'{int(l[0]/divr)}/{int(i/divr)}')

 

---

 

이항 계수 1(#11050)

• Problem

자연수 (N)과 정수 (K)가 주어졌을 때 이항 계수 (NK)를 구하는 프로그램을 작성하시오.

 

• Hint

이항 계수: 조합론에서 이항 계수는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다. 

 

nCk 라고 생각하면 된다! 고등학교떄의 기억을 되짚어보자...

• Solution

조합을 이용한 풀이

from math import factorial
import sys
input=sys.stdin.readline

def binomal(n,k):
    return int(factorial(n)/factorial(n-k)/factorial(k))

a,b=map(int,input().split())

print(binomal(a,b))

고등학교때는,,, 잘 풀었었는데,,

---

 

이항 계수 2(#11051)

• Problem

자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

• Hint

부동소수점에 주의하자.

 

• Solution

부동소수점을 이용한 풀이

from math import factorial
n, k = map(int, input().split())
result = factorial(n) // (factorial(k) * factorial(n - k))
print(result % 10007)

from math import factorial
n, k = map(int, input().split())
result = factorial(n) / (factorial(k) * factorial(n - k))
print(result % 10007)

두 코드의 차이는 무엇일까?

위의 코드는 맞았고 아래의 코드는 틀렸다고한다.

그 이유는 나누셈을 //로 하여 몫을 나오게 하였는지 /로 하여 일반적인 float 나눗셈을 하였는지의 차이인데

 

우리가 알기에도 result 값은 정수형으로 나온다는 사실을 알고 있다는 전제하에 이루어져야한다. 파이썬의 경우 부동소수점 이슈로 이를 조심해서 코딩을 하여야한다.

---

 

다리 놓기(#1010)

• Problem

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

 

• Hint

위의 문제의 형식을 이용해보자. 고등학교의 조합문제

 

• Solution

조합을 이용한 풀이

from math import factorial
cnt=int(input())
res=[]
for i in range(cnt):
    m,n = map(int,input().split())
    result = factorial(n) // (factorial(m) * factorial(n - m))
    res.append(result)
print(*res,sep='\n')

mCn의 형태로 쉽게풀었다.

---

 

패션왕 신해빈(#9375)

• Problem

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

 

• Hint

딕셔너리를 이용해보자. 문제가 이해하기 좀 어렵지만 종류가 무엇이던간에 아무것도 입지 않아서는 안된다 라는 뜻이다.

 

• Solution

딕셔너리를 이용한 풀이

cnt=int(input())
res=[]
for i in range(cnt):
    cnnt=int(input())
    kind={}
    result=1
    for j in range(cnnt):
        a,b = map(str,input().split())
        if b not in kind:
            kind[b]=1
        else:
            kind[b]=int(kind[b]+1)
    for i in kind:
        result*=(kind.get(i)+1)
    res.append(int(result-1))

print(*res,sep='\n')

혹시 궁금해서 숏코딩도 보았지만 상위 코딩도 역시 딕셔너리를 이용하였다.

---

 

팩토리얼 0의 개수(#1676)

• Problem

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

• Solution

from math import factorial

n=int(input())
l=list(map(int,str(factorial(n))))

cnt=0
for i in l[::-1]:
    if i==0:
        cnt+=1
    else:
        print(cnt)
        break

---

 

조합 0의 개수(#2004)

• Problem

$n \choose m$의 끝자리 $0$의 개수를 출력하는 프로그램을 작성하시오.

 

• Hint

0의 개수는 무엇을 뜻하는지 생각해보자

 

• Solution

대수론을 이용한 풀이

from math import factorial
n, k = map(int, input().split())
result = factorial(n) // (factorial(k) * factorial(n - k))
l = list(str(result))
cnt=0
for i in l[::-1]:
    if int(i)==0:
        cnt+=1
    else:
        print(cnt)
        break

처음의 풀이 시간제한이 2초라서 이정도면 되겠지 안일하게 생각했다. 시간초과가 나오는것을 보고 결국엔 0의 개수를 구하라고 하였으니 팩토리얼을 세번 반복하는 과정이 문제라면 두 수에 있는 2와 5 쌍의 개수를 세면 되겠다고 생각되었다.

from math import factorial
n, k = map(int, input().split())
res = factorial(n) // (factorial(k) * factorial(n - k))
cnt=0
res=str(res)
resa=res.rstrip('0')
print(len(res)-len(resa))

이것 마저도 시간초과가 나와서 복잡도를 팩토리얼 세번을 하는 곳에서 줄여야겠구나 생각들었다.

def findfacto(total, a):
    cnt = 0
    while total != 0:
        total = total//a
        cnt += total
    return cnt


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

savetwo = findfacto(n, 2)-findfacto(k, 2)-findfacto(n-k, 2)
savefive = findfacto(n, 5)-findfacto(k, 5)-findfacto(n-k, 5)

print(min(savetwo, savefive))

결국에는 n까지의 숫자중 2가 들어있는 경우와 5가 들어 있는 경우를 새로운 스킬을 이용하여 찾아냈다.

 

원리를 생각해보면 1부터 n까지의 숫자의 나열 내에 있는 a의 제곱수로 이루어진 숫자의 개수는 a와 a의 지수승 들로 n 을 나눈 값의 집합합이다. 라는 사실이다. 이해가 잘 되지 않는다면

 

2의 경우이다. 표를 보고 이해를 해보자