728x90 반응형 1033번1 [백준] 1033번 : 칵테일 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제에서 N - 1개의 비율로 N개의 재료와 관련된 전체 비율을 알아낼 수 있다고 한 것으로 보아 해당 문제를 그래프 관점으로 생각하면 사이클이 없는 트리 구조로 이해할 수 있다. 위 내용을 바탕으로 임의의 시작점에서 DFS를 진행하며 정답을 찾으면 해결할 수 있다. 필요한 재료의 질량을 모두 더한 값이 최소가 되어야 하므로 DFS 과정에서 유클리드 호제법을 활용해 비율들의 최소 공배수와 최대 공약수를 구해 정답에 활용한다. .. 2024. 2. 1. 이전 1 다음 728x90 반응형
