[알고리즘] Java / baekjoon / 양팔저울 / 2629

[알고리즘] Java / baekjoon / 양팔저울 / 2629

문제

문제 링크

접근 방식

1. 입력 받은 추의 무게로 만들 수 있는 무게를 찾는다.
2. 찾은 무게 중에서 구슬 무게가 있다면 Y, 없으면 N을 출력한다.

입력 받은 추의 무게로 만들 수 있는 모든 무게를 찾기 위해 DP를 활용한다.

1. 각 추에 대해 해당 추로 만들 수 있는 모든 무게를 담을 list를 생성한다.
2. 해당 리스트에 현재 추의 무게를 넣는다.
3. 추로 만들 수 있는 모든 무게를 탐색하여 해당 무게가 이전 추로 만들어진 무게라면(이미 방문했다면) 해당 무게에서 현재 추를 더한 무게와 뺀 무게(절댓값)를 리스트에 넣는다.
4. 리스트의 모든 무게를 방문 처리한다.
5. 구슬의 무게가 방문한 무게라면 Y, 아니면 N을 출력한다.

코드

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

public class Main_2629 {

	
	static int Ngrams[], Mgrams[];
	static int[] numbers;
	static int N, M;
	static boolean isCheck;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		
		N = Integer.parseInt(br.readLine()); // 추 개수
		Ngrams = new int[N]; // 추 무게 배열
		
		// 추 입력
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			Ngrams[i] = Integer.parseInt(st.nextToken());
		}
		
		
		M = Integer.parseInt(br.readLine()); // 구슬 개수
		Mgrams = new int[M]; // 구슬 무게 배열
		
		// 구슬 입력
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<M;i++) {
			Mgrams[i] = Integer.parseInt(st.nextToken());
		}
		
		
		
		boolean isValid[] = new boolean[15001];
		
		for(int i=0;i<N;i++) {
			List<Integer> list = new ArrayList<>();
			list.add(Ngrams[i]);
			for(int j=0;j<=15000;j++) {
				if(isValid[j]) {
					if(j+Ngrams[i] <= 15000) list.add(j+Ngrams[i]);
					list.add(Math.abs(j-Ngrams[i]));
				}
			}
			
			for(int j=0;j<list.size();j++) {
				isValid[list.get(j)] = true;
			}
		}
		
		
		StringBuilder sb = new StringBuilder();
		
		for(int i=0;i<M;i++) {
			if(Mgrams[i] > 15000) sb.append("N ");
			else if(isValid[Mgrams[i]]) sb.append("Y ");
			else sb.append("N ");
		}
		
		System.out.println(sb);
		
	}
}