scone-lemon

[Algorithm Study] D4_3234 준환이의 양팔저울 본문

ALGORITHM/SWEA

[Algorithm Study] D4_3234 준환이의 양팔저울

lemon-scone 2021. 9. 1. 22:06

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw&categoryId=AWAe7XSKfUUDFAUw&categoryType=CODE&problemTitle=%EC%96%91%ED%8C%94%EC%A0%80%EC%9A%B8&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com


컨셉만 겨우 이해하고, SubSet 부분이 하이라이트인것 같은데 이부분은 거의 이해를 못했다.
주말에도 안할 것 같지만, 뭔가 주말이 되면 열공할 수 있을 것 같으니까 빨리 주말이 되었으면 좋겠다.

package s0902;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

//준환이의 양팔저울 ver1_clean
//https://data-make.tistory.com/490
public class SWEA_3234_ver1_clean {

	public static int TC, N, result;
	public static int[] w_input, w_output;
	public static boolean[] isSelected;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;

		TC = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= TC; tc++) {

			sb.append("#").append(tc).append(" ");
			N = Integer.parseInt(br.readLine());
			w_input = new int[N];
			w_output = new int[N];
			result = 0;

			st = new StringTokenizer(br.readLine(), " ");
			for (int n = 0; n < N; n++) {
				w_input[n] = Integer.parseInt(st.nextToken());
			}

			isSelected = new boolean[N];
			Permutation(0);
			sb.append(result).append("\n");
		}
		System.out.println(sb.toString());
	}

	private static void Permutation(int cnt) {
		if (cnt == N) {
			SubSet(0,0,0);
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if (isSelected[i]) continue;
			isSelected[i] = true;
			w_output[cnt] = w_input[i];
			Permutation(cnt + 1);
			isSelected[i] = false;
		}
	}

	private static void SubSet(int idx, int sumL, int sumR) {

		if (idx == N) {
			result++;
			return;
		}
		
		SubSet(idx + 1, sumL + w_output[idx], sumR);

		if (sumR + w_output[idx] <= sumL) {
			SubSet(idx + 1, sumL, sumR + w_output[idx]);
		}
	}
}
package s0902;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

//준환이의 양팔저울 ver1
//https://data-make.tistory.com/490
public class SWEA_3234_ver1 {

	public static int TC, N, result;
	public static int[] w_input, w_output;
	public static boolean[] isSelected;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;

		TC = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= TC; tc++) {

			sb.append("#").append(tc).append(" ");
			N = Integer.parseInt(br.readLine()); // 추의 갯수를 저장
			w_input = new int[N]; // 추의 무게들을 입력받아 저장하는 배열
			w_output = new int[N]; // Permutation 결과를 저장하는 배열
			result = 0; // 문제에서 요구하는 경우의 수를 저장

			// 문제에서 요구하는 경우의 수 ?
			// 각 테스트 케이스마다 무게추를 올리는 과정에서
			// 오른쪽 위에 올라가있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 커지지 않는 경우의 수

			st = new StringTokenizer(br.readLine(), " ");
			for (int n = 0; n < N; n++) {
				w_input[n] = Integer.parseInt(st.nextToken());
			}
			//System.out.println(Arrays.toString(w_input));

			isSelected = new boolean[N];
			Permutation(0);
			sb.append(result).append("\n");
		}
		System.out.println(sb.toString());
	}

	/**
	 * 추 줄 세우기 (Permutation 활용)
	 * 구현할 로직 : nPn = N!
	 * @param cnt 순열을 만드는 데에 사용된 추의 갯수
	 */
	private static void Permutation(int cnt) {
		if (cnt == N) {
			System.out.print("\nPermutation's w_output : " + Arrays.toString(w_output) + "\n");
			System.out.println("start SubSet");
			SubSet(0,0,0);
			return;
		}
		for (int i = 0; i < N; i++) {
			if (isSelected[i]) continue;
			isSelected[i] = true;
			w_output[cnt] = w_input[i];
			Permutation(cnt + 1);
			isSelected[i] = false;
		}
	}

	/**
	 * 줄세워진 추 w_output를 저울 양쪽에 올려보기 (SubSet 활용)
	 * @param idx 사용할 추의 인덱스
	 * @param sumL 왼쪽 저울에 올려진 추들의 무게
	 * @param sumR 오른쪽 저울에 올려진 추들의 무게
	 */
	private static void SubSet(int idx, int sumL, int sumR) {

		if (idx == N) {
			// test print (start If)
			// 여기를 탈때마다 result++ = 
			System.out.println("start If (result=" + (result+1) + ")");
			System.out.println("idx : " + idx + ", w_output[idx] : -, sumL : " + sumL + ", sumR : " + sumR);
			// end test print (start If)
			result++;
			return;
		}
		
		// 왼쪽 저울에 해당 인덱스의 추 달기 sumL = sumL + w_output[idx]
		// test print (start SubSet)
		System.out.println("idx : " + idx + ", w_output[idx] : " + w_output[idx] + ", sumL : " + sumL + ", sumR : " + sumR);
		// end test print (start SubSet)
		SubSet(idx + 1, sumL + w_output[idx], sumR);
		
		// 오른쪽에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 크지 않다면
		if (sumR + w_output[idx] <= sumL) {
			
			// 오른쪽 저울에 해당 인덱스의 추 달기 sumR = sumR + w_output[idx]
			// test print (Start SubSet2)
			System.out.println("start SubSet2");
			System.out.println("idx : " + idx + ", w_output[idx] : -, sumL : " + sumL + ", sumR : " + sumR);
			// end test print (Start SubSet2)
			SubSet(idx + 1, sumL, sumR + w_output[idx]);
		}
	}
}

//준환이의 양팔저울 ver2
//https://data-make.tistory.com/490

/* ver1 에서 전역변수로 선언되었던, 

public static int TC, N, result;
public static int[] w_input, w_output;
public static boolean[] isSelected;

TC, result 만 전역변수로 선언해주고,
N, isSelected, weights(w_input, w_output)을 파라미터로 받아준다

ver2는 순열과 부분집합을 동시에 수행하여 해결한 코드이다
이 문제에는 static 변수를 사용하면 시간초과가 나버려서 파라미터로 다 넘겨주어야 한다 (원래는 DP로 풀어내야하는 문제라서...)
파라미터로 다 넘겨주는 이유는 지역변수가 더 빠르게 접근하는 특성을 이용하기 위함이다
=> 공간효율성을 버리고 시간효율성을 얻는 방법! */
package s0902;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
// 준환이의 양팔저울 ver2
// https://data-make.tistory.com/490
public class SWEA_3234_ver2 {
 
   static int TC, result;
   
   public static void main(String[] args) throws IOException {
      
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = null;
      StringBuilder sb = new StringBuilder();
      
      TC = Integer.parseInt(br.readLine());
     
      for (int tc = 1; tc <= TC; tc++) {
         
    	 sb.append("#").append(tc).append(" ");
    	 int N = Integer.parseInt(br.readLine());
         int[] weights = new int[N];
         result = 0;
         
         st = new StringTokenizer(br.readLine());
         for (int i = 0; i < N; i++) {
            weights[i] = Integer.parseInt(st.nextToken());
         }
         
         Permutation_SubSet(0, 0, 0, new boolean[N], weights, N);
         sb.append(result).append("\n");
      }
      System.out.println(sb.toString());
   }
 
   private static void Permutation_SubSet(int idx, int sumL, int sumR, boolean[] isSelected, final int[] weights, int N) {

	   /* ver1 에서 전역변수로 선언되었던, 
	   
	    public static int TC, N, result;
		public static int[] w_input, w_output;
		public static boolean[] isSelected;
		
		TC, result 만 전역변수로 선언해주고,
		N, isSelected, weights(w_input, w_output)을 파라미터로 받아준다
		
		ver2는 순열과 부분집합을 동시에 수행하여 해결한 코드이다
		이 문제에는 static 변수를 사용하면 시간초과가 나버려서 파라미터로 다 넘겨주어야 한다 (원래는 DP로 풀어내야하는 문제라서...)
		파라미터로 다 넘겨주는 이유는 지역변수가 더 빠르게 접근하는 특성을 이용하기 위함이다
		=> 공간효율성을 버리고 시간효율성을 얻는 방법! */
	   
      if(idx == N) {
         result++;
         return;
      }
       
      // 순열과 부분집합을 동시에 수행
      for (int i = 0; i < N; i++) {   
         if(isSelected[i]) continue;
         isSelected[i] = true;

         // 왼쪽 저울에 해당 인덱스의 추 달기 sumL = sumL + w_output[idx] 
         Permutation_SubSet(idx + 1, sumL + weights[i], sumR, isSelected, weights, N);
         
         // 오른쪽에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 크지 않다면
         if(sumR + weights[i] <= sumL) {
        	// 오른쪽 저울에 해당 인덱스의 추 달기 sumR = sumR + w_output[idx]
            Permutation_SubSet(idx + 1, sumL, sumR + weights[i], isSelected, weights, N);
         }
         // 사용한 추를 해제
         isSelected[i] = false;
      }
   }
}

SWEA_3234_ver1_clean.java
SWEA_3234_ver1.java

s0902 SWEA_3234.zip
0.25MB

'ALGORITHM > SWEA' 카테고리의 다른 글

[SWEA D3] 13218. 조별과제  (0) 2023.03.29
[SWEA D3] 12368. 24시간  (0) 2023.03.28
[SWEA D1] 자바 깔짝  (0) 2023.03.27
[Algorithm Study] D3_5215 햄버거 다이어트  (0) 2021.08.31
D2 review  (0) 2021.08.14
'ALGORITHM/SWEA' Related Articles more