코딩 테스트 [정수론] - 칵테일 만들기

august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N은 공개돼 있다. 경근이는 인터넷 검색으로 재료 쌍 N - 1개의 비율을 알아냈고, 이 비율을 이용하면 칵테일에 들어가는 전체 재료의 비율을 알아낼 수 있다. 총 재료 쌍 N - 1개의 비율이 입력으로 주어질 때 다음 조건을 만족하는 칵테일을 만드는 데 필요한 각 재료의 양을 구하는 프로그램을 작성하시오.

· 필요한 재료의 질량을 모두 더한 값이 최소가 되어야 한다.
· 칵테일을 만드는 재료의 양은 정수이고, 총 질량은 0보다 커야 한다.
· 비율은 'a b p q'와 같은 형식으로 주어지는데, a번 재료의 질량을 b번 재료의 질량으로 나눈 값이 p / q 라는 뜻이다.

(시간 제한 2초)

---

입력

1번째 줄에 august14를 만드는 데 필요한 재료의 개수 N이 주어지고, N은 10보다 작거나 같은 자연수다. 2번째 줄부터 N - 1개의 줄에는 재료 쌍의 비율이 1줄에 1개씩 주어지는데, 문제 설명에 나온 형식인 'a b p q'로 주어진다. 재료는 0번부터 N - 1까지이고, a와 b는 모두 N - 1보다 작거나 같은 자연수 또는 0이다. p와 qsms 9보다 작거나 같은 자연수다.

출력

1번째 줄에 칵테일을 만드는 데 필요한 각 재료의 질량을 0번 재료부터 순서대로 공백으로 구분해 출력한다.

예제 입력
5	// 재료 개수
4 0 1 1
4 1 3 1
4 2 5 1
4 3 7 1

예제 출력
105 35 21 15 105

---

1단계 - 문제 분석하기

문제에서는 N - 1개의 비율로 N개의 재료와 관련된 전체 비율을 알아낼 수 있다고 했다. 이것을 그래프의 관점에서 생각하면 사이클이 없는 트리 구조로 이해할 수 있다. 이 내용을 바탕으로 임의의 노드에서 DFS를 진행하면서 정답을 찾으면 된다.
DFS 과정에서 유클리드 호제법을 사용해 비율들의 최소 공배수와 최대 공약수를 구하고, 재료의 최소 질량을 구하는데 사용해 문제를 풀어보겠다.

2단계 - 손으로 풀어 보기

1 인접 리스트를 이용해 각 재료의 비율 자료를 그래프로 구현한다.

2 데이터를 저장할 때마다 비율과 관련된 수들의 최소 공배수를 업데이트한다.

A, B의 최소 공배수는 A * B / 최대 공약수
⇒ 1, 3, 5, 7의 최소 공배수는 105

3 임의의 시작점에 최대 공배수 값을 저장한다.

3 임의의 시작점에서 DFS로 탐색을 수행하면서 각 노드의 값을 이전 노드의 값과의 비율 계산을 통해 계산한고 저장한다.

· 0을 임의의 점으로 선정
⇒ 0에서 DFS로 탐색을 수행하면 0 → 4 → 1 → 2 → 3 순으로 탐색
· 4 ⇒ 0 번 노드값 x 1 / 1 = 105
· 1 ⇒ 4 번 노드값 x 1 / 3 = 35
· 2 ⇒ 4 번 노드값 x 1 / 5 = 21
· 3 ⇒ 4 번 노드값 x 1 / 7 = 15

4 각 노드의 값을 모든 노드의 최대 공약수로 나눈 뒤 출력한다.

105, 35, 21, 15, 105의 최대 공약수는 1
⇒ 각 배열의 값을 1로 나눠 출력 ⇒ 105, 35, 21, 15, 105

3단계 - sudo코드 작성하기

N(재료 개수) A(인접 리스트) lcm(최소 공배수)
D(각 노드값 저장 배열) visited(DFS를 탐색할 때 탐색 여부 저장 배열)

변수 초기화 수행

for(에지 개수)
{
	인접 리스트 배열에 에지 정보 저장
    최소 공배수 업데이트
}

0번 노드에 최소 공배수 저장
0번에서 DFS 탐색 수행
DFS를 이용해 업데이트 된 D 배열의 값들의 최대 공약수 계산
D 배열의 각 값들을 최대 공약수로 나눠 정답 출력

gcd(int a, int b)
{
	if(b == 0)
    	return a;
    else
    	return gcd(b, a % b);
}

DFS
{
	visited 배열에 현재 노드 방문 기록
    현재 노드의 연결 노드 중 방문하지 않은 노드로
    다음 노드의 값 = 현재 노드의 값 * 비율로 저장
    DFS 실행
}

c 노드
{
	다음 노드, 비율 1, 비율 2
}

4단계 - 코드 구현하기

import java.util.ArrayList;
import java.util.Scanner;

public class Q44 {
    static ArrayList<cNode>[] A;
    static long lcm;
    static boolean[] visited;
    static long[] D;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        A = new ArrayList[N];
        visited = new boolean[N];
        D = new long[N];
        lcm = 1;

        for(int i = 0; i < N; i++)
            A[i] = new ArrayList<cNode>();

        for(int i = 0; i < N - 1; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int p = sc.nextInt();
            int q = sc.nextInt();
            A[a].add(new cNode(b, p, q));
            A[b].add(new cNode(a, q, p));
            lcm = lcm * (p * q / gcd(p, q));
        }

        D[0] = lcm;
        DFS(0);
        long mgcd = D[0];
        for(int i = 1; i < N; i++)
            mgcd = gcd(mgcd, D[i]);
        for(int i = 0; i < N; i++)
            System.out.print(D[i] / mgcd + " ");
    }

    private static long gcd(long a, long b){
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }

    private static void DFS(int Node){
        visited[Node] = true;
        for(cNode i : A[Node]){
            int next = i.getB();
            if(!visited[next]){
                D[next] = D[Node] * i.getQ() / i.getP();
                DFS(next);
            }
        }
    }
}
class cNode{
    int b;
    int p;
    int q;

    public cNode(int b, int p, int q) {
        this.b = b;
        this.p = p;
        this.q = q;
    }

    public int getB() {
        return b;
    }

    public int getP() {
        return p;
    }

    public int getQ() {
        return q;
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편