2609. 최대공약수와 최소공배수
https://www.acmicpc.net/problem/2609
내 풀이 - 성공
from sys import stdin
A, B = map(int, stdin.readline().split())
a = set()
b = set()
for i in range(1, A+1):
if A % i == 0:
a.add(i)
for i in range(1, B+1):
if B % i == 0:
b.add(i)
gcd = a & b
print(max(gcd))
print((A*B)//max(gcd))A, B 의 약수들을 각각 a, b 에 저장하고
최대공약수를 구하기 위해 a 와 b 의 교집합 a & b 인 gcd 를 구함
최대공약수는 gcd 의 최댓값
최소공배수는 A*B 를 최대공약수로 나눈 값이라는 것을 이용
다른 사람의 풀이
from sys import stdin
A, B = map(int, stdin.readline().split())
# 최대공약수
def GCD(a, b):
while b:
a, b = b, a%b
return a
# 최소공배수
def LCM(a, b):
result = (a*b) // GCD(a, b)
return result
print(GCD(A, B))
print(LCM(A, B))유클리드 호제법
호제법 = 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘
최대공약수)
a, b 에 대해서 a 를 b 로 나눈 나머지를 r 이라 하면 (단, a>b),
a 와 b 의 최대공약수는 b 와 r 의 최대공약수와 같다는 점을 이용
최소공배수)
a*b 를 최대공약수로 나눈 값
외워두자!!!
1931. 회의실 배정
https://www.acmicpc.net/problem/1931
내 풀이 - 성공
from sys import stdin
N = int(stdin.readline())
arr = []
for i in range(N):
a = list(map(int, stdin.readline().split()))
arr.append(a)
arr.sort(key = lambda x:(x[1], x[0]))
ans = 0
end = 0
for s, e in arr:
if end <= s or e < end:
end = e
ans += 1
print(ans)회의 종료 시간이 관건이므로
회의 시간을 담은 리스트 arr 을 종료 시간 기준으로 정렬
=> 종료 시간이 우선이되 시작 시간도 정렬되어야 함
그리고 회의 시간을 하나씩 보면서
종료시간이 현재 범위에 포함되지 않으면 같은 룸에서 회의가 가능하다는 것이므로 ans + 1
전에 leetcode 에선 못 풀었던 것 같은데 이번엔 풀어서 굿~
Hello, World!