백준 1033 파이썬 DFS와 최대공약수

2024. 6. 3. 06:18코딩 도구/백준

반응형

백준 1033 - 칵테일

문제

https://www.acmicpc.net/problem/1033

 

1033번: 칵테일

august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다.  경근이는 인터넷 검색을 통해서 재료 쌍 N

www.acmicpc.net

1033번

답안 코드 :

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):
    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=' ')

생각 :

# 문제 분석
# N -1 개 비율로 N개 비율을 알 수 있다 ?
# 그래프 관점으로 생각 -> 사이클 없는 트리 구조
# 그러면 임의의 노드에서 DFS 진행하면서 정답 찾기
# DFS과정에서 유클리드 호제법을 사용해서
# 비율들의 최소 공배수와 최대 공약수 구하고
# 재료의 최소 질량을 구해보자 .....

# 문제 풀이
# 인접리스트로 각 재료의 비율자료를 그래프로 구현
# 데이터 저장 떄마다 비율 관련 최소 공배수 업데이트
# 임의의 시작점에 최대 공배수 값 저장
# 시작점에서 DFS로 탐색 : 각 노드의 값을 이전 노드의 값과의 비율 계산
# 각 노드의 값을 모든 노드의 최대 공약수로 나눠서 출력

 

정수론 정리 글들

 

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B1%84

 

정수론 : 소수 구하기 에라토스테네스의 채

소수 소수 구하기의 핵심 이론 소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체를 들 수 있다. 에라토스테네스의 체 원리는 다음과 같다. ① 구하고자 하는 소수의 범위만큼 1차원 리

mkisos.tistory.com

 

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%98%A4%EC%9D%BC%EB%9F%AC-%ED%94%BC

 

정수론 : 오일러 피

오일러 피 오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 오일러 피 함수는 증명 과정을 공부해야 완벽하게 알 수 있다고하지만 실제 코딩 테스트에

mkisos.tistory.com

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

 

정수론 : 유클리드 호제법

유클리드 호제법 유클리드 호제법 euclidean-algorithm은 두 수의 최대 공약수를 구하는 알고리즘이다. 일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현

mkisos.tistory.com

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%ED%99%95%EC%9E%A5-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

 

정수론 : 확장 유클리드 호제법

확장 유클리드 호제법 유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것이다. 확장 유클리드 호제법을 제대로 이해하

mkisos.tistory.com

 

반응형