[SWEA] 3234. 준환이의 양팔저울(순열,부분집합).java

#. Problem

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw

* 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

예시를 보면

추들이 올라갈 때 순서가 있는 것을 볼 수 있다.

Right   2

Left    1, 4

Right   2

Left    4, 1

는 다른 경우이다.

그렇기 때문에 순열로 추들을 세워둔 후

순서대로 추들을 왼쪽 혹은 오른쪽에 올려보면서

무게를 비교해보아야 한다.

#. 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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer;   public class Solution3234_v2 {       static int T, N, res, arr[], weight[];     static boolean used[];          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  T = Integer.parseInt(br.readLine());         for (int tc = 1; tc <= T; tc++) {             res = 0;             N = Integer.parseInt(br.readLine());             arr = new int[N];             weight = new int[N];                          st = new StringTokenizer(br.readLine());             for (int i = 0; i < N; i++) {                 arr[i] = Integer.parseInt(st.nextToken());             }                          used = new boolean[N];             balances(0);                          System.out.println("#" + tc + " " + res);         }       }          /**      * 추 줄 세우기      * @param cnt    순열에 사용된 추의 개수      */     private static void balances(int cnt) {         // 모든 추를 세웠다면         if(cnt == N) {             check(0, 0, 0);             return;         }                   // 세울 수 있는 추의 경우(순열)         // N개 중 N개를 세울 경우. nPn = N!         for (int i = 0; i < N; i++) {             // 이미 사용된 추라면 pass             if(used[i]) continue;             // 이 추를 사용해보자.             used[i] = true;             weight[cnt] = arr[i];             balances(cnt + 1);             // 지금 사용 안 해볼래.             used[i] = false;         }     }       /**      * 세워진 추를 사용해서 저울에 올려보자.       * @param idx    사용할 추의 index      * @param sumL    왼쪽 저울에 올려진 추들의 무게      * @param sumR    오른쪽 저울에 올려진 추들의 무게      */     private static void check(int idx, int sumL, int sumR) {         // 모든 추를 저울에 다 올렸다면         if(idx == N ) {             res++;             return;         }         // 왼쪽 저울에 해당 idx 추를 올려보자.         check(idx + 1, sumL + weight[idx], sumR);         // 오른쪽 저울에 올려진 추들의 무게가 왼쪽에 올라가 있는 추들의 무게보다 작다면         // 오른쪽에 해당 idx 추를 올려보자.         if(sumR + weight[idx] <= sumL)             check(idx + 1, sumL, sumR + weight[idx]);     } } Colored by Color Scripter

cs

#. Code_v2

순열과 부분집합을 동시에 수행하여 해결한 코드이다.

이 문제에는 static 변수를 사용하면 시간초과가 나버려서

파라미터로 다 넘겨주어야 한다. (원래는 DP로 풀어내야하는 문제라서...)

* 파라미터로 다 넘겨주는 이유는 지역변수가 더 빠르게 접근하는 특성을 이용

 -> 공간효율성을 버리고 시간효율성을 얻는 방법!

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 54 55 56 57 58

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class Solution3234 {      static int T, res;        public static void main(String[] args) throws IOException {              BufferedReader br = new BufferedReader(new InputStreamReader(System.in));       StringTokenizer st;              T = Integer.parseInt(br.readLine());       for (int tc = 1; tc <= T; tc++) {          res = 0;          int N = Integer.parseInt(br.readLine());          int[] arr = new int[N];                    st = new StringTokenizer(br.readLine());          for (int i = 0; i < N; i++) {             arr[i] = Integer.parseInt(st.nextToken());          }                    balances(0, 0, 0, new boolean[N], arr, N);                    System.out.println("#" + tc + " " + res);       }      }      private static void balances(int idx, int sumL, int sumR, boolean[] used, final int[] arr, int N) {       // 모든 추를 올렸다면       if(idx == N) {          res++;          return;       }               // 순열과 부분집합을 동시에 수행       for (int i = 0; i < N; i++) {             // 이미 사용된 추일 경우 pass          if(used[i]) continue;          // 해당 추를 사용해보자.          used[i] = true;          // 왼쪽 저울에 해당 추를 올려볼까          balances(idx + 1, sumL + arr[i], sumR, used, arr, N);                    // 오른쪽에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 크지 않다면          if(sumR + arr[i] <= sumL) {             // 오른쪽 저울에 해당 추를 올려볼까             balances(idx + 1, sumL, sumR + arr[i], used, arr, N);          }          // 사용한 추를 해제          used[i] = false;       }    } } Colored by Color Scripter

cs