[python] 단계별로 풀어보기 - 17단계

 

백준 17단계 정수론 및 조합론

 

https://www.acmicpc.net/step/18

 

 

참고로 검문(2981) 문제는 풀지 못했다

보통 계속 생각해보다가 답이 안나오면 구글링을 해서 다른 분들의 풀이를 참고하는 편이다.

그러면 보통 이해가 잘 가는 편인데, 수학적인 요소가 많이 담겨있다보니 이해가 잘 가지 않는다..

어떻게 풀이하면 저런 식이 나오는지 잘 이해가 안됐다.

그렇다고해서 그냥 문제만 해결해두면 절대절대 다시 안볼걸 알기 때문에 일단 풀지 않고 넘겼다

 

나중에 코딩실력도 쌓이고 코딩테스트를 다시 제대로 준비 할 시기가 되면 다시 도전해보려고한다

 

 

 

---

 

 

17-1) 백준 5086번: 배수와 약수

 

 

a, b = map(int, input().split())
while a!= 0 and b != 0:
    if a<b:
        if b%a == 0:
            print("factor")
        else:
            print("neither")

    else:
        if a%b == 0:
             print("multiple")
        else:
            print("neither")
    a, b = map(int, input().split())

 

 

수를 입력 받은 뒤, 둘 다 0이 들어올 때 까지 반복한다.

그래서 a가 b보다 작을 경우는 약수만 나올 수 있으니, 만약 나누어지면 약수를 의미하는 factor를 출력한다. 만약 factor가 아니면 자연스럽게 neither이 된다.

그리고 a가 b보다 클 경우에는 배수만 나올 수 있으므로,

위와 비슷하게 생각하여 각각에 의미하는 것을 출력해주면 된다.

 

 

 

 

 

 

 

17-2) 백준 1037번: 약수

 

a = int(input())
k = list(map(int, input().split()))

m = max(k)
n = min(k)

print(m*n)

 

N을 구하려면 입력받은 약수들 중에서 가장 큰 수와 가장 작은 수를 구해서 곱해주면 된다.

문제는 돌려돌려 말해서 헷갈릴 수 있지만, 진짜 원하고자 하는 값을 생각하면 쉽게 풀 수 있었다.

 

 

 

 

 

 

 

17-3) 백준 2609번: 최대공약수와 최소공배수

 

import math
a,b = map(int, input().split())
gcd = math.gcd(a,b)
print(gcd)
print(a*b//gcd)

 

math를 import하여 사용하면 최대공약수를 구할 수 있는 gcd함수를 사용할 수 있다.

최소공배수는 최대공약수를 활용해서 구할 수 있다. 두 수의 곱을 최대공약수로 나눠주면 최소공배수가 된다.

위의 문제 풀이 방법을 알고있으면 쉽게 해결가능했다.

 

 

 

 

 

 

17-4) 백준 1934번: 최소공배수

 

import math
T = int(input())
for i in range(T):
    a,b = map(int, input().split())
    gcd = math.gcd(a,b)
    print(a*b//gcd)

 

위와 동일한 방식으로 푸는데, 최대공약수를 제외한 최소공배수만 출력해주면 된다.

 

 

 

 

 

 

 

17-6) 백준 3036번: 링

 

def gcd(a, b):
    while(b!=0):
        n = a % b
        a = b
        b = n
    return a


N = int(input())
num = list(map(int, input().split()))

for i in range(1, len(num)):
    g = gcd(num[0], num[i])
    
    print('{0}/{1}'.format(num[0]//g, num[i]//g))

 

최대공약수를 구해준 뒤, 그 수로 나눈 수를 출력해주면 된다.

 

사실 최대공약수를 구해서 풀어야한다는 것을 생각하지 못해서 구글링하여

다른 분들의 코드를 참고해서 다시 풀었다.

 

 

 

 

 

 

17-7) 백준 11050번: 이항 계수1

 

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

result = math.factorial(N)//(math.factorial(K)*math.factorial(N-K))
print(result)

 

이항 계수의 식을 알면 그대로 쓰면 된다.

math함수를 import해주면 factorial을 쓸 수 있다.

사실 math함수를 import하여 쓰는 것은 시간초과가 뜨지 않을까 싶었는데, 정답이 떠서 조금은 놀랐다

 

이항 계수를 구하는 식은 

nCk = C(n,k) = n!/(n-k)!k!

이다.

 

 

 

 

 

 

17-8) 백준 11051번: 이항 계수2

 

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

result = math.factorial(N)//(math.factorial(K)*math.factorial(N-K))
print(result%10007)

 

위의 문제와 동일한데 결과에서 10007로 나눈 나머지를 출력해주면 된다. 

 

 

 

 

 

 

17-9) 백준 1010번: 다리 놓기

 

import math

T = int(input())
for i in range(T):
    N, K = map(int, input().split())
    result = math.factorial(K)//(math.factorial(N)*math.factorial(K-N))
    print(result)

 

이게 도대체 뭘 묻고 싶은 문제인가 싶었는데, 알고보니 조합을 사용하여 구하는 문제였다

문제 파악만 하면 쉽게 풀 수 있는 문제 였다.

왜 수학 공부도 같이 해라고 하는지 납득 가능했던 것 같다.

 

 

 

 

 

 

17-10) 백준 9375번: 패션왕 신해빈

 

#(종류별 옷의 수) + 1을 전부 곱해주고 (해당 종류의 옷을 안 입는 경우의 수를 포함한 것) 
# 아무것도 입지 않은 경우의 수인 1 빼기
K = int(input())

for _ in range(K):
    n = int(input())
    
    # 0일때 종료
    if n == 0:
        print(0)
        continue
    
    wearable = dict()
    for _ in range(n):
        name, kind = map(str, input().split())
        
        # 옷의 종류있으면 됨
        if kind in wearable.keys():
            wearable[kind] += 1
        else:
            wearable[kind] = 1
        
        #(각 옷의 수)+1 한 것을 곱해줌
        answer = 1
        for key in wearable.keys():
            answer *= wearable[key] + 1
            
    #안입는 경우만 뺴줌
    print(answer - 1)

 

이거도 어떻게 풀어야하나하다가 구글링하여 다른 분들의 코드를 참고한 것이다.

주석을 많이 달았으므로 자세한 설명을 생략하겠다.

문제를 보고 수학적으로 접근하는 방법도 공부해야겠다고 생각했다.

 

 

 

 

 

 

17-11) 백준 1676번: 팩토리얼 0의 개수

 

import math

count = 0
T = int(input())
N = math.factorial(T)

while(N % 10 == 0):
    N = N//10
    count += 1
print(count)

 

위에서 썼던 방식으로 팩토리얼을 사용하여 값을 구해준다.

그 후, 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구해야하므로

10으로 나눈 나머지가 0일때만 구하면 된다. (맨 뒤에 나오는 수가 0이라는 것)

그리고 그 반복문 안에서 10으로 나눈 뒤, N에 다시 넣어주고 count를 해주면 된다

 

만약 N이 20100이라면 

10으로 나누었을 때 나머지가 0이므로 반복문 안으로 들어간다

그럼 20100을 10으로 나눈 몫이 2010이다. 즉, N은 2010이라는 것이다

다음으로 count는 1이 된다

 

그럼 다시 N이 2010이 되는데

10으로 나눈 나머지가 0이므로 다시 반복문 안으로 들어가고

N은 201이 되고, count는 2가 된다

 

그럼 이제 201은 10으로 나누어떨어지지 않으므로 count가 2가 되고 끝이난다.

 

 

 

 

 

 

17-12) 백준 2004번: 조합 0의 개수

 

# 0의개수
# M!가 가지고 있는 2의 개수 - N!이 가지고 있는 2의 개수 - (M-N)!이 가지고 있는 2의 개수
# /
# M!가 가지고 있는 5의 개수 - N!이 가지고 있는 5의 개수 - (M-N)!이 가지고 있는 5의 개수
# 중에 작은 수

   
#n!의 5 개수 세는 함수
def five_count(n):
    answer = 0
    while n != 0:
        n = n // 5
        answer += n
    return answer

#n!의 2 개수 세는 함수
def two_count(n):
    answer = 0
    while n != 0:
        n = n // 2
        answer += n
    return answer


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

if m == 0:
    print(0)
    
else:       
    print(min(two_count(n)-two_count(m)-two_count(n-m), five_count(n)-five_count(m)-five_count(n-m)))

 

이 문제도 이렇게 풀어야하는 방법을 몰라서 방황하다가 검색해서 알았다.

앞으로 저렇게 푸는 법은 외워야할 것 같다..!

 

 

 

 

 

 

---

 

 

 

코딩을 배우면서 수학적인 요소가 왜 필요한지 잘 이해를 못했다

하지만 이번 챕터를 풀어보면서 수학의 중요성을 다시 깨닫게 되었다

 

저런 공식이 있는줄도 몰랐는데 다양한 것을 많이 접하게 되었던 것 같다

앞으로 수학적으로 접근하는 것도 많이 생각을하며 코딩테스트를 준비해야겠다