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

8월 14일(월) - 다이나믹 프로그래밍 (2629번)

2629번: 양팔저울

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

(C언어 풀이 활용)

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

import java.util.StringTokenizer;

public class Main {

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

        num_of_weight = Integer.parseInt(br.readLine());
        weight = new int[num_of_weight + 1];
        dp = new int[num_of_weight + 1][40001];

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

        solve(0, 0);

        int num_of_bead = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<num_of_bead; i++)
        {
            int bead = Integer.parseInt(st.nextToken());

            if(bead > 15000)
            {
                sb.append("N ");
            }
            else if(dp[num_of_weight][bead] == 1)
            {
                sb.append("Y ");
            }
            else
            {
                sb.append("N ");
            }
        }

        System.out.print(sb);
    }

    static void solve(int i, int w){
        if(i > num_of_weight || dp[i][w] == 1)
        {
            return;
        }

        dp[i][w] = 1;
        solve(i+1, w);
        solve(i+1, w + weight[i]);
        solve(i+1, Math.abs(w - weight[i]));
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ