[백준] 2629번 양팔저울 풀어보기 [Java]

관계식이 있는 dp문제였다. 관계식만 잘 구하면 잘풀수 있어 골드3까지는 아닌거 같다!!(내가 뭐라고 평가하나,,,,ㅋㅋㅋ)

 

👨‍🏫 풀이

나는 세가지 경우를 나눠서 풀었다.

1. 지금 추를 더하는 경우

2. 지금 추를 더하지 않고 넘어가는 경우

3. 지금의 무게가 추보다 작다면, 추에서 현재 무게를 빼고, 크다면, 현재 무게에서 추를 뺀다.

 

Base case

1. weight 음수가 되면 안되고(원래 0이 될일도 없기 때문에 0을 포함해줘야 됐지만, 나는 첫 시작 무게를 0으로 설정을 해줘서 0을 포함해주지 않았다.) 40000보다 크면 안된다.

2. 주어진 추는 한번만 사용가능하기 때문에 주어진 추를 다 방문했는지 체크

 

👨🏻‍💻 코드

package 번2629;

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

public class Main {
    static int N;
    static int[] chu;
    static int num;
    static int[] gusul;
    static boolean[][] cache;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        chu = new int[N];
        for(int i = 0 ; i < N ; i++){
            chu[i] = Integer.parseInt(st.nextToken());
        }
        num = Integer.parseInt(br.readLine());
        gusul = new int[num];
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < num ; i++) {
            gusul[i] = Integer.parseInt(st.nextToken());
        }
        cache = new boolean[N+1][40001];
        dp(0,0);
        for(int i = 0 ; i < num ; i++) {
            boolean isPossible = false;
            for(int j = 0 ; j < N+1 ; j++) {
                if(cache[j][gusul[i]]) {
                    System.out.print("Y ");
                    isPossible = true;
                    break;
                }
            }
            if(!isPossible) System.out.print("N ");
        }
    }

    private static void dp(int n, int weight) {
        if(weight < 0 || weight > 40000) return;
        if(cache[n][weight]) return;
        cache[n][weight] = true;
        if(n == N) return;

        dp(n + 1, weight + chu[n]);//현재꺼를 더하는 경우
        dp(n + 1, weight); // 현재꺼를 더하지 않는 경우
        dp(n + 1, (weight < chu[n]) ? chu[n] - weight : weight - chu[n]); // 현재꺼를 빼는 경

    }
}