백준 1033 : 칵테일

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

1033번: 칵테일

 

해결 방법 : 연립 방정식...? (+ 최소공약수)

• 주어진 재료 비율 정보를 순차적으로 받으면서 연립 계산이 가능하다면 연립하여 비율 갱신
• 이전에 갱신에 사용된 행은 다음 연립에 사용 할 필요 X
  • skip 리스트에 저장해서 무시하도록 한다
• 마지막 비율 정보까지 계산이 끝나면 최대공약수로 나누어 재료의 총량을 최소화

 

import sys
input = sys.stdin.readline

def solution(N, ratios):
    M = [[None] * N for i in range(N-1)] # [재료1, 재료2, ...] * (비율 정보 개수)
    skip = [] # 아래의 어떤 row와 합쳐진 row 번호 저장
    for i in range(N-1): # 각 재료 비율 정보 개수만큼,
        x, y, xv, yv = ratios[i] # 재료1, 재료2, 재료1 양, 재료2 양
        M[i][x], M[i][y] = xv, yv # M의 i번째 리스트에 위 정보 저장

        for j in range(i): # i이전의 행을 참고하여, 연립 갱신이 가능한 비율 정보 탐색
            if j in skip: continue # j행이 이미 어떤 행(j< any row <i)의 연립에 사용됨, skip

            # 연립 갱신
            excep1 = [] # M[j]의 여집합 재료
            excep2 = [] # M[i]의 여집합 재료
            inter = None # M[i]와 M[j]의 공통 재료
            for k in range(N): # 각 재료(N개) 탐색
                if M[i][k] is not None and M[j][k] is not None:
                    inter = k
                elif M[j][k] is not None:
                    excep1.append(k)
                elif M[i][k] is not None:
                    excep2.append(k)

            if inter is not None: # 만약 공통 재료가 있다면 -> 연립 갱신 가능
                skip.append(j) # j행은 이번 갱신에서 사용되었으므로 skip에 추가
                temp = M[i][inter] # (M[i][inter]값이 사용되기 전에 갱신 될 수 있으므로..)
                for e in range(N): # 각 재료
                    if e in excep1: # 만약 j행의 여집합 재료이면,
                        M[i][e] = M[j][e] * temp 
                    if e in excep2 or e == inter: # i행(현재 행)의 여집합 재료 or 공통 재료
                        M[i][e] = M[i][e] * M[j][inter]

    # minimize
    def gcd(a, b): # 두 수의 최대공약수 반환
        return a if b == 0 else gcd(b, a % b)
    answer = M[-1] 
    gcd_ = answer[0]
    for i in answer: # 모든 재료에 대한 최대공약수 계산
        gcd_ = gcd(gcd_, i)
    answer = ' '.join([str(int(i / gcd_)) for i in answer]) # 최대공약수로 나누기

    return answer

if __name__ == '__main__':
    N = int(input())
    ratios = [list(map(int, input().strip().split())) for i in range(N-1)]
    result = solution(N, ratios)
    print(result)