[Python/BOJ] 1954. 화학실험

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

1954번: 화학실험

문제

우리에게는 n가지 종류의 화학 시약 t1, t2, ..., tn과 M mg의 용액이 있다. 이 용액 중 x mg을 시약 ti에 넣으면 aix+bi만큼의 어떤 가스가 발생한다고 한다. 시약에 넣을 수 있는 용액의 양은 자연수이다.

우리가 할 일은 이렇다. M mg의 용액을 적절히 n가지 종류의 시약에 넣어서 각각의 시약에서 같은 양의 가스를 발생시키려 한다. 예를 들어 a1=3, b1=5, a2=4, b2=3, a3=1, b3=7 이라고 하자. 그리고 용액이 M = 27mg이라고 하자. 그러면 첫 번째 시약에 6mg, 두 번째 시약에 5mg, 세 번째 시약에 16mg을 넣으면 세 개의 시약 모두 23mg이 발생하게 된다. 하지만 M=26일 경우에는 이렇게 세 개의 시약 모두 같은 양의 가스를 발생시키는 것이 불가능 하다.

시약의 개수 n과 용액의 양 M, 그리고 a1, a2, ..., an과 b1, b2, ..., bn이 주어져 있을 때, 만약에 n개의 시약 모두 같은 양의 가스를 발생 시킬 수 있으면 그 가스의 양을 출력하고, 그럴 수 없으면 0을 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 시약의 종류 n(1 ≤ n ≤ 100)이 주어진다. 그리고 두 번째 줄부터 n+1번째 줄까지 공백을 사이에 두고 ai와 bi가(1 ≤ ai ≤ 100, 1 ≤ bi ≤ 1000) 주어진다. 그리고 n+2번째 줄에는 용액의 양 M(1 ≤ M ≤ 10000) 이 주어진다.

출력

만약에 n개의 시약 모두 같은 양의 가스를 발생시키는 것이 가능하면 첫 번째 줄에 그 가스의 양을 출력하고, 그것이 불가능하면 첫째 줄에 대신 0을 출력하여라.

풀이

Code

import sys
input = sys.stdin.readline

def solution(n, array, total) :
    # 1. 조합 함수 정의
    def combination(target, now) :
        # 1-1.
        for a, b in array :
            # 필요한 만큼 시약 감소
            now -= (target - b) / a
        # 1-2. 시약의 양이 부족하다면 0 출력
        if now < 0 : print(0); exit()
        # 1-3. 정확히 목표 가스 양을 사용했다면 결과 출력 후 종료
        if now == 0 : print(target); exit()

    # 2. 최소 시작 값 정의
    target = 1
    # 3.
    while True :
        combination(target, total)
        target += 1

if __name__ == "__main__":
    n = int(input())
    array = [list(map(int, input().split())) for _ in range(n)]
    total = int(input())
    solution(n, array, total)