[백준] 2629번. 양팔 저울 (java)

www.acmicpc.net/problem/2629

2629번: 양팔저울

왠지 dp문제인 거 같은데 어떻게 업데이트할지 몰라서 반복문으로 돌리며 나오는 경우의 수를 arraylist에 넣고 

flag변수로 해당 구슬 무게가 되는지 확인했다 다행히 통과

 

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int n,m;// 추의 개수 구슬의 개수 
	static int[] chu;//추
	static int[] ball;//구슬
	static boolean[] flag=new boolean[40001];//구슬 무게는 40000까지 가능
	static ArrayList<Integer> arr=new ArrayList<>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		chu=new int[n]; //추의 무게 
		arr.add(0);//처음 계산하기 위한 수 0을 넣어준다.
		flag[0]=true; // 무게의 차가 0인 것을 초기화해서 true
		for (int i = 0; i < n; i++) {
			chu[i]=sc.nextInt();		
		}
		m=sc.nextInt();
		ball=new int[m];
		for (int i = 0; i < m; i++) {
			ball[i]=sc.nextInt();
		}
		
		for (int i = 0; i < n; i++) {
			int size=arr.size(); //앞의 추에서 이미 계산한 무게만큼만 돌려준다.
			for (int j = 0; j < size; j++) { //앞에 계산된 무게에서 현재 무게를 더하고 빼는 경우 구해준다.
				int x=arr.get(j);//계산된 무게 중 하나 
				if(x+chu[i]<=40000 && flag[x+chu[i]]==false) {//이전까지 가능한 무게에서 더했을 때
					arr.add(x+chu[i]); //새로운 무게 더해줌 
					flag[x+chu[i]]=true;
				}
				if(flag[Math.abs(x-chu[i])]==false) {// 현재 추의 무게와 이전에 계산된 무게들의 차
					arr.add(Math.abs(x-chu[i]));
					flag[Math.abs(x-chu[i])]=true;
				}
			}
		}
	
		for (int i = 0; i < m; i++) {
			if(flag[ball[i]]) { //계산되었던 수라면 가능하다 y
				System.out.print("Y ");
			}else {
				System.out.print("N ");
			}
		}
	}
	
	
}