[SWEA] 5215. 햄버거 다이어트(부분집합).java

#. Problem

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT&categoryId=AWT-lPB6dHUDFAVT&categoryType=CODE

* The copyright in this matter is in SWEA

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

정해진 칼로리 이하의 조합 중에서 민기가 가장 선호하는 햄버거를 조합해주어야 한다고 했다.

주어진 제한 칼로리 이하의 재료 조합 중에서 맛에 대한 점수가 가장 높은 햄버거의 점수를 찾아야 한다.

여기서, 우리는 어떤 재료를 사용해보고, 사용해보지 않을 지

사용해볼 수 있는 재료에 대한 모든 경우를 부분집합으로 생각해야 한다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class Solution {       static int N, L, maxScore;     static int[][] material;       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;         int T = Integer.parseInt(br.readLine());           for (int tc = 1; tc <= T; tc++) {             st = new StringTokenizer(br.readLine(), " ");             N = Integer.parseInt(st.nextToken());    // 재료 수             L = Integer.parseInt(st.nextToken());    // 제한 칼로리               material = new int[N][2];               // 재료 정보             for (int i = 0; i < N; i++) {                 st = new StringTokenizer(br.readLine(), " ");                 material[i][0] = Integer.parseInt(st.nextToken()); // 점수                 material[i][1] = Integer.parseInt(st.nextToken()); // 칼로리             }               maxScore = 0;             selectMaterial(0, 0, 0);               System.out.println("#" + tc + " " + maxScore);         }     }       public static void selectMaterial(int idx, int scr, int cal) {         // 칼로리 초과         if (cal > L) return;         // 주어진 제한 칼로리 이하의 조합         if (cal <= L) maxScore = Math.max(maxScore, scr);         // 모두 조합을 확인         if (idx == N) return;                  // 이 재료를 사용해보자         selectMaterial(idx + 1, scr + material[idx][0], cal + material[idx][1]);         // 이 재료는 사용하지 않을래         selectMaterial(idx + 1, scr, cal);     }   }   Colored by Color Scripter

cs