백준 / 2629 / 양팔저울 / java

첫 시도

package backjun.M동적계획2;

import java.util.Scanner;
import java.util.HashSet;

public class 양팔저울 {
    static HashSet<Integer> set;
    static int[] bead;
    static int n;

    static void dfs(int left, int right, int x){
        int tmp = Math.abs(right - left);
        set.add(tmp);

        if(x==n){
            return;
        }

        dfs(left+bead[x], right, x+1);
        dfs(left, right+bead[x], x+1);
        dfs(left, right, x+1);
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        bead = new int[n];

        for(int i=0; i<n;i++){
            bead[i] = sc.nextInt();
        }

        set = new HashSet<>();

        dfs(0, 0, 0);
        
        n = sc.nextInt();
        for(int i=0; i<n;i++){
            int t = sc.nextInt();
            if(set.contains(t))
                System.out.print("Y ");
            else
                System.out.print("N ");
        }
    }
}

메모리 초과가 났다.
메모리 초과 원인을 파악해보면 구슬에 대해 dfs 진행할 때 같은 구슬에 대해서 무게가 같은 경우일 때도 dfs를 진행할 경우가 존재한다. 위 코드는 static으로 dfs 함수를 선언했으므로 중복된 dfs를 계속 진행하면 메모리 초과가 발생할 수 있게된다.

따라서 dp를 통해 해당 구슬에 대해서 dfs 진행하기 전에 같은 연산을 수행한 적이 있는지를 파악해야한다.
즉 dp를 통해 값을 누적한는것이 아니라 방문 여부를 확인한다.
(이 방식을 dp라고 부르는게 맞나??)

수정 코드

package backjun.M동적계획2;

import java.util.Scanner;
import java.util.HashSet;

public class 양팔저울 {
    static HashSet<Integer> set;
    static int[] bead;
    static int n;
    static int[][] dp;

    static void dfs(int left, int right, int x){
        int tmp = Math.abs(right - left);
        set.add(tmp);

        if(x==n){
            return;
        }

        if(dp[x][tmp] == 0) {
            dfs(left+bead[x], right, x+1);
            dfs(left, right+bead[x], x+1);
            dfs(left, right, x+1);
            dp[x][tmp] = 1;
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        bead = new int[n];

        for(int i=0; i<n;i++){
            bead[i] = sc.nextInt();
        }

        set = new HashSet<>();
        dp = new int[n][30*500+1];

        dfs(0, 0, 0);
        
        n = sc.nextInt();
        for(int i=0; i<n;i++){
            int t = sc.nextInt();
            if(set.contains(t))
                System.out.print("Y ");
            else
                System.out.print("N ");
        }
    }
}