백준_2961_도영이가 만든 맛있는 음식

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

• DFS, 완전 탐색

• 신맛과 쓴맛을 저장한 배열을 하나씩 방문하며 넣을지 안 넣을지 확인한다

• 모든 음식을 넣을지 안 넣을지 확인하였을 때, 쓴맛과 신맛의 차이가 answer보다 작다면 answer를 업데이트

- 완전 탐색 후 answer를 출력

첫풀이

import java.util.*;
import java.io.*;

public class Main {
    static int N;
    static int[] S;
    static int[] B;
    static int ans = Integer.MAX_VALUE;
    static int nowS, nowB;

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

        S = new int[N];
        B = new int[N];

        nowS = 1; // 신맛의 곱
        nowB = 0; // 쓴맛의 합

        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            S[i] = Integer.parseInt(st.nextToken());
            B[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0);

        System.out.print(ans);
    }

    private static void dfs(int i) {
        if (i == N) {
            if (nowS != 1) { // 아무 재료도 선택하지 않았을 경우
                ans = Math.min(ans, Math.abs(nowS - nowB));
            }
            return;
        }

        nowS = nowS * S[i];
        nowB = nowB + B[i];
        dfs(i + 1);

        nowS = nowS / S[i];
        nowB = nowB - B[i];
        dfs(i + 1);
    }
}

• 아무 재료도 선택하지 않았을 경우를 고려하는게 중요한 문제였다!
  boolean 배열을 따로 두지않고 초기값을 활용하여 재료가 적어도 1개 이상인지 확인 할 수 있었다!

최적화

import java.util.*;
import java.io.*;

public class Main {
	static int N;
	static int[] S;
	static int[] B;
	static int ans = Integer.MAX_VALUE;

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

		for(int i = 0; i < N; i++){
			StringTokenizer st = new StringTokenizer(br.readLine());
			S[i] = Integer.parseInt(st.nextToken());
			B[i] = Integer.parseInt(st.nextToken());
		}

		dfs(0, 0, 1, 0);

		System.out.print(ans);
	}
	static void dfs(int idx, int cnt, int nowS, int nowB) {
		if(idx == N){
			if (cnt >= 1) {
				ans = Math.min(ans, Math.abs(nowS - nowB));
			}
			return;
		}

		dfs(idx + 1, cnt + 1, nowS * S[idx], nowB + B[idx]);

		dfs(idx + 1, cnt, nowS, nowB);
	}
}

• dfs 함수의 매개변수로 현재 신맛의 곱(nowS)과 쓴맛의 합(nowB)을 전달
  👉 전역 변수를 사용하는 것보다 오류를 줄이고, 각 호출마다 상태를 명확하게 관리할 수 있을 듯