[Java] 백준 2629번: 양팔저울

[문제 바로 가기] - 양팔저울

📌 유형 : DFS

💡 아이디어

아래 적은 첫 풀이에서 하지 못한 중복 체크를 위해 dp 배열을 2차원을 선언해주었다. (dp[추개수][측정가능한무게])

dfs를 통해 weights 배열에 있는 추들의 무게를 1. 더하고(+) 2. 빼고(-) 3. 사용하지 않을 경우를 체크해준다. 이때, idx를 통해 해당 상태를 이미 탐색했는지 체크한다.

또한 문제에서 구슬의 무게가 40,000보다 작거나 같은 자연수라고 되어있는데, (추의 최대 개수) x (추의 최대 무게)가 15,000이다.

따라서 N일 경우는 1. 구슬의 무게가 15,000보다 클 경우 2. 가지고 있는 추의 조합으로 측정할 수 없을 경우가 된다.
Y일 경우는 가지고 있는 추의 조합으로 측정할 수 있는 경우, 즉 possible[marble]이 true일 때다.

그리고 시행착오..

2
1 4
2
3 2

dp[1] = true -> dp[4] = true -> dp[3] = true, dp[5] = true와 같은 진행으로 true인 값들에 +, - 해가려고 했는데 메모리 초과가 떴다.

내 풀이는 중복 체크 없이 계속 값을 리스트에 추가하므로 메모리 초과가 날 수 밖에 없었다.

---

풀이

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

public class Main {
	public static boolean[][] dp;
	public static boolean[] possible;
	public static int[] weights;
	public static int N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		weights = new int[N];
		dp = new boolean[N + 1][15001];
		possible = new boolean[15001];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < N; i++) {
			weights[i] = Integer.parseInt(st.nextToken());
		}
		
		dfs(0, 0);
		
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < M; i++) {
			int marble = Integer.parseInt(st.nextToken());
			if (marble > 15000) sb.append("N ");
			else sb.append(possible[marble] ? "Y " : "N ");
		}
		
		System.out.println(sb);
	}
	
	public static void dfs(int idx, int w) {
		if (idx > N || dp[idx][w]) return;
		
		dp[idx][w] = true;
		possible[w] = true;
		
		if (idx == N) return;
		
		dfs(idx + 1, w + weights[idx]);
		
		dfs(idx + 1, Math.abs(w - weights[idx]));
		
		dfs(idx + 1, w);
	}
}