BOJ_1954 : 화학실험

👉 문제링크

1954번: 화학실험

---

---

🔸 문제 분석 🔸

• n 종류의 화학 시약 t1, t2, ..., tn의 정보 ai와 bi, 그리고 M mg의 용액이 주어진다.
  • 용액 중 x mg을 시약 ti 에 넣으면 ai*x+bi 만큼의 가스가 발생한다.
  • n개의 화학 시약 모두 같은 양의 가스를 발생시킬 수 있으면 가스 양을 출력하고, 그럴 수 없으면 0을 출력한다.
  • 용액이 남으면 안된다.
• 용액의 양 x mg 을 1부터 늘려가며 용액들에 넣어보고 같은 양의 가스가 발생하는 경우가 있는지 모두 확인해야 한다.
  • 경우의 수 확인 중, 모두 같은 양의 가스가 발생하는 경우를 찾으면 그 가스 양을 출력하고 종료한다.
  • 끝까지 탐색해도 같은 양의 가스가 발생하는 경우가 없으면 0을 출력한다.

🔸 코드 🔸

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

public class Main {
    static int n, m;
    static int[] a;
    static int[] b;

    private static boolean recursion(int idx, int ml, int befor_gas) {
        if (idx == n) {
            return ml == 0;
        }

        for (int i = 1; i <= ml-(n-idx-1); i++) {
            int now_gas = a[idx]*i+b[idx];
            if (now_gas == befor_gas && recursion(idx+1, ml - i, befor_gas)) {
                return true;
            } else if (now_gas > befor_gas) {
                break;
            }
        }
        return false;
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        a = new int[n];
        b = new int[n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            a[i] = Integer.parseInt(st.nextToken());
            b[i] = Integer.parseInt(st.nextToken());
        }

        m = Integer.parseInt(br.readLine());

        int answer = 0;
        for (int i = 1; i <= m - n + 1; i++) {
            int gas = a[0]*i+b[0];
            if (recursion(1, m-i, gas)) {
                answer = gas;
                break;
            }
        }
        System.out.println(answer);
    }
}

🔸 코드 해석 🔸

• main 메서드에서 n개의 시약 정보와 용액의 양 m을 입력받는다.
• 용량 m을 1부터 m-(n-1) 까지 키워가며 계산한다.
  • recursion 메서드를 호출하고, true가 반환 되면 정답에 gas를 저장하고 반복을 종료한다.
• recursion 메서드는 (현재 고른 시약 수 idx, 남은 용액 ml, 이전에 나온 가스 befor_gas) 를 인자로 받으면 ture,false를 반환한다.
  • idx가 n이 되면, 남은 용액이 0이면 ture, 아니면 false를 반환한다. (용액이 남으면 안된다)
  • for문에서는 idx번째 시약에 넣을 용액을 1부터 ml-(n-idx-1) 까지 넣어본다.
    • 나온 가스 now_gas가 이전 가스 befor_gas와 같으면, 다시 recursion 메서드에 다음 시약을 확인한다.
    • true가 반환 되면, 똑같이 true를 반환한다.
    • 만약 now_gas>befor_gas라면, 시약을 더 넣어도 더 많은 가스가 나올 것이므로 now_gas==befor-gass인 상황이 오지 않는다. 따라서 break로 빠져나온다.
    • false를 반환한다.

---

🔸 end 🔸

• 용액의 양을 어떻게 조절해야 하나 고민하다가, 모든 경우를 다 따져야 할 것 같아서 재귀 메서드를 사용했다.
• 재귀 메서드의 반복 횟수 최적화를 위해 for문의 종료 조건을 지정하는게 어려웠던 것 같다.
• 문제 분석과 풀이 계획을 적어가며 풀이했다.