우매함의 봉우리를 넘어서며 개발하면서 기록하기

백준 2961. 도영이가 만든 맛있는 음식

24 Feb 2021

문제 바로가기

도영이가 만든 맛있는 음식

문제 요약

도영이는 재료 N개를 가지고 있고 각 재료의 신맛 S와 쓴맛 B를 알고있는 상태에서 새로운 요리를 하려고 한다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고 쓴맛은 재료의 쓴맛의 합이다.

신맛과 쓴맛을 조화롭게 만들기 위해서 그 차이를 가장 작게 만들어야 하며 재료는 적어도 1개 이상 사용해야 한다.

이때, 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력하는 프로그램을 만들어라.

문제 풀이 포인트

  1. 문제를 보자마자 조합을 사용할 생각을 해야한다. 최소 1개 이상 최대 모두 다 사용할 수 있기 때문에 각 상황에 맞게 조합을 활용해서 재료의 신맛과 쓴맛의 차를 구한다.

  2. 재귀를 활용하면 더 간단하게 구현이 가능하다. 변수 k를 활용하여 재료의 배열 중 k번째에 있는 재료를 사용할지 사용하지 않을지 선택하게 구현할 수 있다.
    • 선택할 경우: 신맛의 합과 쓴맛의 합에 선택한 재료의 신맛과 쓴맛 또한 더하여 다음 함수에 전달한다.
    • 선택하지 않을 경우: 신맛의 합과 쓴맛의 합을 그대로 다음 함수에 전달한다.
  3. 2번의 과정을 변수 k가 전체 재료 배열의 길이까지 도달하면 재귀를 끝마친다.

문제 코드[JAVA]

코드 펼치기 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  static class Taste{
    int sin, sseun;

    public Taste(int sin, int sseun) {
      super();
      this.sin = sin;
      this.sseun = sseun;
    }

  }
  static Taste[] arr;
  static int N, ans = Integer.MAX_VALUE;
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(in.readLine());
    N = Integer.parseInt(st.nextToken());
    arr = new Taste[N];
    for(int i = 0; i < N; i++) {
      st = new StringTokenizer(in.readLine());
      arr[i] = new Taste(Integer.parseInt(st.nextToken()), 
      Integer.parseInt(st.nextToken()));
    }
    func(0, 1, 0);
    System.out.println(ans);

  }
  static void func(int k, int sin_sum, int sseun_sum) {
    if(k == arr.length) {
      if(sin_sum > 1 && sseun_sum > 0) {
        //System.out.println(sin_sum + " " + sseun_sum);
        ans = Math.min(ans, Math.abs(sin_sum-sseun_sum));
      }
      return;
    }
    // 현재 위치의 재료를 선택할 경우
    func(k+1, sin_sum*arr[k].sin, sseun_sum+arr[k].sseun);
    //현재 위치의 재료를 선택하지 않을 경우
    func(k+1, sin_sum, sseun_sum);
  }
}

Related posts