[BOJ/JAVA] 백준 2961번 : 도영이가 만든 맛있는 음식

2961번: 도영이가 만든 맛있는 음식

 

 

 

---

 

 

 

• 풀이

 

문제는 신맛, 쓴맛의 재료만 있고 신맛과 쓴맛의 조합은 최대 10가지가 있습니다.

조합을 할때마다 신맛끼리는 곱해지고, 쓴맛끼리는 더해집니다.

적절히 조합하여 신맛과 쓴맛의 절대값차이가 가장 적은 수를 구하면 되는 문제입니다.

 

일단 조합은 최대 10가지로 모든 경우의 수를 확인하는 완탐방식을 생각했습니다. 시간은 1초이고, 10!의 시간으로 완전탐색은 1초안에 될 것이라고 생각했습니다.

 

참고로 이 문제는 비트마스킹으로 조금 더 쉽게 구현할 수 있습니다.

 

비트마스킹의 방법은 1 << N을 함으로써 2^N번을 바깥 for문을 통해서 확인합니다.

0000

0001

0010

0011

0100

0101

....

1111

이런식으로 N개의 수 중 택한 경우는 1, 택하지않은 경우는 0으로 모든 경우의 수를 확인할 수 있게합니다.

안쪽 for문에서는 0~3까지의 수를 반복함으로써 바깥 for문의 1의 자리, 2의 자리, 3의 자리, 4의 자리의 숫자가 1인지 0인지 확인하고, 1이면 신맛, 쓴맛 추가 0이면 작없을 하지 않는 방법으로 진행합니다.

 

 

• 코드

 

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	static int N;
	static long answer;
	static boolean[] check;
	static ArrayList<Flavor> flavor;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		check = new boolean[N];
		answer = Integer.MAX_VALUE;
		flavor = new ArrayList<>();
		for (int i = 0; i < N; i++)
			flavor.add(new Flavor(in.nextInt(), in.nextInt()));
		dfs(0);
	}

	private static void dfs(int index) {
		if (index == N) {
			int sour = 1;
			int bitter = 0;
			int count = 0;
			for (int i = 0; i < check.length; i++) {
				if (!check[i])	continue;
				count++;
				sour *= flavor.get(i).sour;
				bitter += flavor.get(i).bitter;
			}
			if (count == 0)
				return; 
			
			if (answer > Math.abs(sour - bitter))
				answer = Math.abs(sour - bitter);
			return;
		}
		
		check[index] = true;
		dfs(index + 1);
		check[index] = false;
		dfs(index + 1);
	}
}

class Flavor {
	int sour;
	int bitter;

	public Flavor(int sour, int bitter) {
		this.sour = sour;
		this.bitter = bitter;
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

 

 

• 비트마스킹 코드

 

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	static int N;
	static long answer;
	static boolean[] check;
	static ArrayList<Flavor> flavor;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		check = new boolean[N];
		answer = Integer.MAX_VALUE;
		flavor = new ArrayList<>();
		for (int i = 0; i < N; i++)
			flavor.add(new Flavor(in.nextInt(), in.nextInt()));
		
		for(int i = 1; i < 1 << N; i++) {
			int sour = 1, bitter = 0;
			for(int j = 0; j < N; j++) {
				if((i & 1<<j) > 0) {
					sour *= flavor.get(j).sour;
					bitter += flavor.get(j).bitter;
				}
			}
			answer = Math.min(answer, Math.abs(sour-bitter));
		}
	}
}

class Flavor {
	int sour;
	int bitter;

	public Flavor(int sour, int bitter) {
		this.sour = sour;
		this.bitter = bitter;
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}