[JAVA] 백준 2961

 

 

 

2961번: 도영이가 만든 맛있는 음식

 

문제

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

풀이

해당 문제는 백트래킹을 통해서 탐색하면서 신맛과 쓴맛의 차이가 최소가 되는 값을 반환하는 문제다.

먼저 이 문제를 기본적인 boolean 배열을 사용해서 문제를 풀어보았다.

📌 boolean[]으로 문제 해결

import java.io.*;
import java.util.Arrays;

class Main {
    static boolean[] V;
    static int MIN = 1_000_000_001;
    static int N;
    static int[][] A;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        V = new boolean[N];

        A = new int[N][2];
        for(int i=0; i<N; i++){
            String[] value = br.readLine().split(" ");

            A[i][0] = Integer.parseInt(value[0]);
            A[i][1] = Integer.parseInt(value[1]);
        }
        DFS(0, 1, 0);
        System.out.println(MIN);
    }

    public static void DFS(int depth, int value1, int value2){

        if(depth > 0){
            MIN = Math.abs(value1 - value2) < MIN ? Math.abs(value1 - value2) : MIN;
        }

        for(int i=0; i<N; i++){
            if(!V[i]){
                V[i] = true;
                DFS(depth + 1, value1 * A[i][0], value2 + A[i][1]);
                V[i] = false;
            }
        }

    }
}

모든 경우를 탐색하면서 값을 찾았다.

이 경우에 시간과 메모리 사용량은 다음과 같다.

📌 int 비트 마스킹

다음은 비트 마스킹을 통해서 boolean 배열 대신 int를 사용해서 풀었다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Main {
    static int visit;
    static int[][] A;
    static int N;
    static int min = 1_000_000_001;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        A = new int[N][2];

        for(int i=0; i<N; i++){
            String[] value = br.readLine().split(" ");

            A[i][0] = Integer.parseInt(value[0]);
            A[i][1] = Integer.parseInt(value[1]);
        }
        DFS(0, 0, 1, 0);
        System.out.println(min);

    }

    public static void DFS(int depth, int now, int value1, int value2){
        if(depth > 0) min = Math.min(min, Math.abs(value1 - value2));

        for(int i=now; i<N; i++){
            if(!((visit & (1 << i)) == (1 << i))){
                visit |= (1 << i);
                DFS(depth+1, i, value1 * A[i][0], value2 + A[i][1]);
                visit &= ~(1 << i);
            }
        }
    }
}

방식은 같은 방식이고 비트 마스킹 기법을 사용해서 visit 배열을 제거한 차이밖에 없다.

결과는 다음과 같다.

3배 정도 속도가 빨랐으며 메모리 사용량의 차이는 별로 없었다.

📌 자료형 char로 비트 마스킹

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Main {
    static char visit = 0;
    static int[][] A;
    static int N;
    static int min = 1_000_000_001;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        A = new int[N][2];

        for(int i=0; i<N; i++){
            String[] value = br.readLine().split(" ");

            A[i][0] = Integer.parseInt(value[0]);
            A[i][1] = Integer.parseInt(value[1]);
        }
        DFS(0, 0, 1, 0);
        System.out.println(min);

    }

    public static void DFS(int depth, int now, int value1, int value2){
        if(depth > 0) min = Math.min(min, Math.abs(value1 - value2));

        for(int i=now; i<N; i++){
            if(!((visit & (1 << i)) == (1 << i))){
                visit |= (1 << i);
                DFS(depth+1, i, value1 * A[i][0], value2 + A[i][1]);
                visit &= ~(1 << i);
            }
        }

    }

}

결과는 다음과 같다.

메모리 사용량의 약간의 감소가 보였다.

결과

백트래킹 문제에 비트 마스킹을 적용시켰을 때 어느정도의 시간과 메모리 차이가 나는지 확인해볼 수 있었다.

비트 마스킹을 적용하면 속도 측면에서 상당한 차이를 보였고 메모리에는 큰 차이는 없었다.

boolean

int

char