[BOJ - JAVA] 2961 - 도영이가 만든 맛있는 음식(브루트포스)

# 주소

https://www.acmicpc.net/problem/2961

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

# 문제

# 문제 해설 및 코드 리뷰

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n;
    static int[][] arr;
    static int sum = Integer.MAX_VALUE;
    static boolean visit[];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n][2];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 2; j++){
                arr[i][j] = scan.nextInt();
            }
        }
        visit = new boolean[n];
        for(int i = 1; i <= n; i++){
            dfs(i,0);
            visit = new boolean[n];
        }
        System.out.println(sum);
    }
    static void dfs(int cnt, int k){
        if(k == cnt){
            sum = Math.min(check(), sum);
            return;
        }
        for(int i = 0; i < n; i++){
            if(!visit[i]) {
                visit[i] = true;
                dfs(cnt, k + 1);
                visit[i] = false;
            }
        }
    }
    static int check(){
        int a = 1;
        int b = 0;
        for(int i = 0; i < n; i++){
            if(visit[i]){
                a = a * arr[i][0];
                b = b + arr[i][1];
            }
        }
        return Math.abs(a-b);
    }
}

이제 브루트포스풀이도 거의 막바지를 향해가고 있습니다.

실제 블로그에 담지 못하는 내용이 정말 많지만 지금까지 제 블로그에 담긴 문제들의 양도 적은건 아니니 충분히 도움될 것이라 생각합니다.

살펴보도록 하겠습니다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
arr = new int[n][2];
for(int i = 0; i < n; i++){
    for(int j = 0; j < 2; j++){
        arr[i][j] = scan.nextInt();
    }
}

늘 그랬듯이 이번에도 입력문은 Scanner로 받았습니다.

arr를 2차원 배열로 받되 [n][2]크기로 받았습니다.

신 맛과 쓴 맛을 [i][0], [i][1]에 받을 것입니다.

제가 표현하고 싶은건, 1개를 골랐을 때의 dfs, 2개를 골랐을 때의 dfs,... 쭉 가서 n개를 골랐을 때의 dfs를 해보고 싶습니다. 그러기 위해서 모든 경우에 대해 dfs를 실행해보아야 할 것입니다.

그래서 전

visit = new boolean[n];
for(int i = 1; i <= n; i++){
    dfs(i,0);
    visit = new boolean[n];
}
System.out.println(sum);

for문으로 i = 1부터 n까지 총 n번 시행하였습니다.

첫 번째 파라미터로 들어갈 i는 백트래킹을 하여 목표로 할 시행 횟수이고 0은 현재 시행 횟수를 의미합니다

static void dfs(int cnt, int k){
    if(k == cnt){
        sum = Math.min(check(), sum);
        return;
    }
    for(int i = 0; i < n; i++){
        if(!visit[i]) {
            visit[i] = true;
            dfs(cnt, k + 1);
            visit[i] = false;
        }
    }
}

그러므로 dfs의 구성은 다음과 같습니다.

만약 k를 cnt만큼 진행했을 때 sum의 값은 check()와 sum의 최솟값을 비교할 건데 이건 나중에 살펴보고, for문부터 보겠습니다.

if(!visit[i]){ } -> 만약 방문하지 않은 인덱스라면(처음 방문하는 것이라면)

visit을 true로 바꾸고 dfs(cnt, k+1); 을 실행하며 다음단에는 visit을 다시 false로 바꿉니다.

이렇게 로직을 짤 경우 각 횟수에 대한 모든 조합에 대해 탐색할 수 있습니다.

만약 cnt가 2이고 n이 4개라면

(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3) 이렇게 탐색 가능합니다.

그럼 이렇게 탐색한 결과를 check()함수로 개수를 셀텐데, check()함수는

static int check(){
    int a = 1;
    int b = 0;
    for(int i = 0; i < n; i++){
        if(visit[i]){
            a = a * arr[i][0];
            b = b + arr[i][1];
        }
    }
    return Math.abs(a-b);
}

전 이렇게 구성했습니다.

a = 1, b = 0으로 두었습니다.

a는 신 맛이기 때문에 계속해서 곱해야 하고 b는 계속해서 더해야 하므로 1과 0으로 두어야 합니다.

그리고 만약 for문으로 만약 방문한 인덱스라면 a에는 계속해서 arr[i][0]값을 곱할 것이고 b에는 계속해서 arr[i][1]을 더할 것입니다.

그렇게 해서 계산된 결과 값을 Math.abs(a-b)로 return하고 min값을 최소로 갱신해주면 그것이야 말로 정답이 되겠습니다.

감사합니다.