[JAVA] 백준 #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을 출력하여라.

 

입출력 예제

문제풀이

총 용액 배분: 1~M까지 순열로 배분하기      -> 처음에는 모든 1~M순열 구해서 시간 초과 발생     -> 가스양 확인해서 같지 않으면  return 으로 시간초과 해결

 

n-1개 순열로 하고 나머지 1개는 sum-지금까지의 합으로 정해주기

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main{
	static int n;
	static int[] arr;
	static int gas[][];
	static int m;
	static int result;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n =Integer.parseInt(br.readLine());// 시약 종류
		arr = new int[n]; // 시약에 넣는 용액 양 x
		gas = new int[2][n]; // a,b저장

		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			gas[0][i] = Integer.parseInt(st.nextToken());
			gas[1][i] = Integer.parseInt(st.nextToken());
		}
		m = Integer.parseInt(br.readLine());// 총 용액의 양
		perm(0,0,0);
		System.out.println(result);
	}

	private static void perm(int cnt, int sum,int r) {
		if (cnt == n - 1) {
			arr[cnt] = m - sum;
				if (cnt==0 || r == gas[0][cnt] * arr[cnt] + gas[1][cnt]) {
					result=gas[0][cnt] * arr[cnt] + gas[1][cnt];
					}
			return;
		}

		for (int i = 1; i <= m; i++) {
			arr[cnt] = i;
			if(cnt ==0) r=gas[0][0] * arr[0] + gas[1][0];
			if(r!=gas[0][cnt] * arr[cnt] + gas[1][cnt]) continue;
			perm(cnt + 1, sum + i,r);
			if(result!=0) return;
		}
	}
}