[BOJ]2629 - 양팔저울 (G3)

suhyun·2023년 3월 1일
0

백준/프로그래머스

목록 보기
80/81

문제 링크

2629-양팔저울


입력

첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다.
둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다.
같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있다.

세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다.
네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 빈 칸이 하나씩 있다. 확인하고자 하는 구슬의 무게는 40,000보다 작거나 같은 자연수이다.

출력

주어진 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N 을 차례로 출력한다.
출력은 한 개의 줄로 이루어지며, 각 구슬에 대한 답 사이에는 빈칸을 하나씩 둔다.


문제 풀이

무게를 확인해야하는 구슬이 항상 왼쪽에 있다고 가정하면 항상 아래 3가지의 경우 중 하나로 나타난다.

  1. 구슬을 왼쪽에 추가 (w+weights[i])
  2. 구슬을 오른쪽에 추가 (|w-weights[i]|)
  3. 올리지 않음 (w)

이 경우의 수를 가지고 for문을 돌려서 해결해도 되지만
나는 재귀를 이용했다.

이 문제에서 주의해야하는 점은
추의 무게는 500g이하, 갯수는 30개 이하이므로 추를 가지고 셀 수 있는 무게는 최대 15000g이다.
확인하려는 무게는 40000g 이하이므로 15000g 초과에 대해서는 확인하지않아도 결과값이 N 이다.
즉, dp 배열에 대해서 15000까지만 확인하면 불필요한 연산을 줄일 수 있다.

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

public class Main {
    static int N, M;
    static int[] weights;
    static boolean[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        weights = new int[N];
        dp = new boolean[N+1][15001];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            weights[i] = Integer.parseInt(st.nextToken());
        }

        findDP(0, 0);

        M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());

            if(num > 15000) sb.append("N ");
            else sb.append(dp[N][num] ? "Y " : "N ");
        }
        System.out.println(sb);
    }

    static void findDP(int n, int w) {
        if(dp[n][w]) return;

        dp[n][w] = true;
        if(n == N) return;

        findDP(n + 1, w + weights[n]);
        findDP(n + 1, w);
        findDP(n + 1, Math.abs(w - weights[n]));
    }
}
profile
꾸준히 하려고 노력하는 편 💻

0개의 댓글