G2629. 양팔저울

문제

제출 코드

• 사용 알고리즘 : dp

완탐하면 메모리 초과 난다고 한다.

4월 월말평가 2번문제였는데, DP인걸 알았지만 어떻게 풀지 고민하는 시간이 오래걸렸다.

추를 하나씩 올려가면서 계산해야 한다는 것은 알았지만 구현하기가 헷갈렸다.

DP문제는 무조건 이차원 배열로 점차적으로 쌓아간다는 고정관념을 깨게 해준 문제였다.

저울의 양쪽 모두를 저장한다고 생각하지 않고, 이후 구슬이 올라가지 않을 쪽의 추의 무게만 저장했다.

이전에 저장된 경우에다 현재 추를 올려고보고, 내려보았고 이 중 저장되지 않은 값은 저장하는 방식으로 구현하였다.

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 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 1. 추 정보 입력받기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] ball = new int[N];	// 추 정보 저장해둘 배열 생성
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) ball[i] = Integer.parseInt(st.nextToken());

		// 2. 순서대로 추 올려보기
		// result = 저울에 추를 올릴때, 구슬이 올라가지 않을 저울에 올라갈 수 있는 모든 무게를 저장함
		List<Integer> result = new ArrayList<>(); // 확인 가능한 무게 저장해둘 리스트 생성
		result.add(0);	// 아무런 추도 올려놓지 않은 경우 넣어두기
		for(int i=0; i<N; i++) {
			int size = result.size(); // 이전 추들을 모두 고려했을때 나온 경우의 수
			for(int j=0; j<size; j++) {	// 이전 경우의 수들에 지금 추까지 새로 고려하기
				int num = result.get(j)+ball[i];	// 현재 추를 구슬이 올라갈 반대방향에 추가하는 경우
				if(!result.contains(num)) result.add(num);
				num = Math.abs(result.get(j)-ball[i]);// 현재 추를 구슬과 같은 쪽에 추가하는 경우
				if(!result.contains(num)) result.add(num);
			}
		}

		// 3. 무게확인 가능한지 판단 후 출력
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<M; i++) {
			if(result.contains(Integer.parseInt(st.nextToken()))) sb.append("Y");
			else sb.append("N");
			if(i+1!=M) sb.append(" ");
		}
		System.out.println(sb);
	}
}