[Java] 백준 2961 도영이가 만든 맛있는 음식

2961 도영이가 만든 맛있는 음식 문제 링크

문제

#1

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][2];
        StringTokenizer st;
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        int min = Integer.MAX_VALUE;
        for(int i=0; i<N; i++) {
            int a = 1;
            int b = 0;
            for(int j=i; j<N; j++) {
                a = a * arr[j][0];
                b = b + arr[j][1];
                min = Math.min(min, a-b > 0 ? a-b : b-a);
            }
        }
        System.out.println(min);
    }
}

• 모든 조합을 거쳐야 함
• 이중 for문으로 배열을 돌렸는데, 이건 연속된 배열만 고려하게 됨
• 재귀를 활용해서 모든 조합을 구하도록 해야함

#2

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

class Main {
    static int[][] arr;
    static int N;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][2];
        StringTokenizer st;
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        tasteSel(0, 1, 0, 0);
        System.out.println(min);
    }

    static void tasteSel(int level, int s, int b, int selCount) {
        if(level==N) {
            if(selCount>0) {
                min = Math.min(min, Math.abs(s-b));
            }
            return;
        }
        tasteSel(level+1, s*arr[level][0], b+arr[level][1], selCount+1);
        tasteSel(level+1, s, b, selCount);
    }
}

• 모든 조합을 도는 게 어려워서 블로그 참고함..
  참고 블로그
• tasteSel() 안에서 tasteSel()를 두 번 호출
  • 한 번은 해당 level을 선택한 경우, 한 번은 선택하지 않은 경우로
  • 모든 수를 거친 후에 하나 이상을 선택한 경우에만 차이가 작은 값을 찾아서 min에 넣어줌