📌 문제 043) 최대 공약수 구하기
시간 제한 2초, 실버 II, 백준 1850번
모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.
예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.
입력
첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 2^63보다 작은 자연수이다.
3 4 # A와 B의 길이
출력
첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다.
1
1단계 문제 분석
- 수의 길이를 나타내는 두 수의 최대 공약수는 A와 B의 최대 공약수의 길이를 나타낸다.
- 즉, 3, 6의 최대 공약수 3은 A(111)와 B(111111)의 최대 공약수(111)의 길이로 나타난다.
- 유클리드 호제법을 이용해 주어진 A, B의 최대 공약수를 구한다.
- 공약수의 길이만큼 1을 반복해 출력한다.
ex) 500000000000000002 % 500000000000000000 = 2
500000000000000000 % 2 = 0
최대 공약수가 2이므로 2번 반복해 1을 출력함 -> 11
2단계 슈도 코드
# 최대 공약수 gcd() 함수 구현
gcd(a, b):
if b가 0이면:
a가 최대 공약수
else:
gcd(작은 수, 큰 수 % 작은 수) # 재귀 함수 형태로 구현
a(1번째 수), b(2번째 수)
결괏값 = gcd(a, b)
결괏값 크기만큼 1 반복 출력3단계 코드 구현
def gcd(a, b):
if b ==0:
return a
else:
return gcd(b, a % b)
a, b = map(int, input().split())
result = gcd(a, b)
while result > 0: # result 값만큼 반복하여 1 출력
print(1, end='')
result -= 1📌 문제 044) 칵테일 만들기
시간 제한 2초, 골드 II, 백준 1033번
august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다.
경근이는 인터넷 검색을 통해서 재료 쌍 N-1개의 비율을 알아냈고, 이 비율을 이용해서 칵테일에 들어가는 전체 재료의 비율을 알아낼 수 있다.
총 재료 쌍 N-1개의 비율이 입력으로 주어진다. 이때, 칵테일을 만드는데 필요한 각 재료의 양을 구하는 프로그램을 작성하시오.
- 필요한 재료의 질량을 모두 더한 값이 최소가 되어야 한다.
- 칵테일을 만드는 재료의 양은 정수이고, 총 질량은 0보다 커야한다.
- 비율은 "a b p q"와 같은 형식이고, a번 재료의 질량을 b번 재료의 질량으로 나눈 값이 p/q라는 뜻이다.
입력
첫째 줄에 august14를 만드는데 필요한 재료의 개수 N이 주어지며, N은 10보다 작거나 같은 자연수이다.
둘째 줄부터 N-1개의 줄에는 재료 쌍의 비율이 한 줄에 하나씩 주어지는데, 문제 설명에 나온 형식인 "a b p q"로 주어진다. 재료는 0번부터 N-1까지이며, a와 b는 모두 N-1보다 작거나 같은 음이 아닌 정수이다. p와 q는 9보다 작거나 같은 자연수이다.5 # 재료 개수 4 0 1 1 # 1:1 4 1 3 1 # 3:1 4 2 5 1 # 5:1 4 3 7 1 # 7:1
출력
첫째 줄에 칵테일을 만드는데 필요한 각 재료의 질량을 0번 재료부터 순서대로 공백으로 구분해 출력한다.
105 35 21 15 105
1단계 문제 분석
- N-1개의 비율로 N개의 재료와 관련된 전체 비율을 알아낼 수 있다고 했다.
- 그래프 관점으로 생각하면 사이클이 없는 트리 구조로 이해할 수 있다.
- 임의의 노드에서 DFS를 진행하면서 정답을 찾으면 된다.
- DFS 과정에서 유클리드 호제법을 사용해 비율들의 최소 공배수와 최대 공약수를 구하여, 재료의 최소 질량을 구하는 데 사용하자.
- 인접 리스트를 이용해 각 재료의 비율 자료를 그래프로 구현한다.
- 데이터를 저장할 때마다 비율과 관련된 수들의 최소 공배수를 업데이트한다.
- A, B의 최소 공배수는 AxB / 최대 공약수
ex) 1, 3, 5, 7의 최소 공배수는 105
- 임의의 시작점에 최소 공배수 값을 저장하낟.
- 임의의 시작점에서 DFS로 탐색을 수행하며 각 노드의 값을 이전 노드의 값과 비율 계산을 통해 계산하고 저장한다.
- 0을 임의의 점으로 선정
- DFS로 0->4->1->2->3 순으로 탐색
- 4 -> 0번 노드값 * 1/1 = 105
- 1 -> 4번 노드값 * 1/3 = 35
- 2 -> 4번 노드값 * 1/5 = 21
- 3 -> 4번 노드값 * 1/7 = 15
- 각 노드의 값을 모든 노드의 최대 공약수로 나눈 뒤 출력한다.
- 105, 35, 21, 15, 105의 최대 공약수는 1
- 각 리스트의 값을 1로 나눠 출력
-> 105 35 21 15 105
2단계 슈도 코드
N(재료의 개수)
A(인접 리스트)
visited(DFS를 탐색할 때 탐색 여부 저장 리스트)
D(각 노드값 저장 리스트)
lcm(최소 공배수)
# 최대 공약수 gcd() 함수 구현
gcd(a, b):
if b가 0이면:
a가 최대 공약수
else:
gcd(작은 수, 큰 수 % 작은 수) # 재귀 함수 형태로 구현
# 탐색 함수 구현
DFS:
visited 리스트에 현재 노드 방문 기록
if 현재 노드의 연결 노드 중 방문하지 않은 노드:
다음 노드의 값 = 현재 노드의 값 * 비율로 저장
DFS(다음 노드) # 재귀 형태
for 에지 개수:
인접 리스트에 이 에지 정보를 저장
최소 공배수 업데이트
0번 노드에 최소 공배수 저장
0번에서 DFS 탐색 수행
DFS를 이용해 업데이트 된 D 리스트의 값들의 최대 공약수 계산
D 리스트의 각 값을 최대 공약수로 나눠 정답 출력3단계 코드 구현
N = int(input())
A = [[] for _ in range(N)]
visited = [False] * (N)
D = [0] * (N)
lcm = 1
def gcd(a, b): # 최대 공약수 함수 구현
if b ==0:
return a
else:
return gcd(b, a % b)
def DFS(v): # DFS 탐색 함수 구현
visited[v] = True
for i in A[v]:
next = i[0]
if not visited[next]:
D[next] = D[v] * i[2] // i[1] # // : 몫 연산자
DFS(next)
for i in range(N-1):
a, b, p, q = map(int, input().split())
A[a].append((b, p, q))
A[b].append((a, q, p))
lcm *= (p * q // gcd(p, q)) # 최소 공배수는 두 수의 곱을 최대 공약수로 나눈 것
D[0] = lcm
DFS(0)
mgcd = D[0]
for i in range(1, N):
mgcd = gcd(mgcd, D[i])
for i in range(N):
print(int(D[i] // mgcd), end=' ')