3234. 준환이의 양팔저울 D4

🅰 SWExpert 3234. 준환이의 양팔저울

SW Expert Academy

✏️ 문제 풀이

• 남아있는 무게를 오른쪽에 더해봤을 때 left보다 작으면 어차피 모든 부분에 적용 가능하기 때문에 따로 순열을 탐색 할 필요 없이, 나머지 케이스 수 만큼 sum에 더하고 backtracking을 하면 시간을 더 줄일 수 있다.
• 또한 비트마스킹을 이용하여 데이터를 관리하면 시간을 더 줄일 수 있다.
• JAVA언어 / 23,396 kb메모리 / 1,357 ms실행시간 / 1,555코드길이의 결과가 나왔다.
• np를 이용하여 들어온 데이터에 대한 모든 순열을 뽑아냈고, dfs 함수 안에서 기저조건으로는 추가 모두 놓아지고 왼쪽무게>=오른쪽무게 일 때 종료되기로 했다.
• 오른쪽 추를 놓을 수 있는지, 왼쪽 추 놓을 수 있는지 확인 후 가능하면 무게를 추가하고 함수를 재귀돌려주었다. 
• 재귀함수가 종료되었을 때 left,rightSum한 값을 빼줘서 추가한 추의 무게를 빼줬다.

✏️ 소스코드

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

public class Solution_D4_3234_손은성 {
	static int leftSum;
	static int rightSum;
	static int input[];
	static int N;
	static int cnt;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int i = 1; i <= T; i++) {
			N = Integer.parseInt(br.readLine());
			input = new int[N];
			int sum = 0;
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				input[j] = Integer.parseInt(st.nextToken());
			}
			
			Arrays.sort(input);
			do {
				leftSum+=input[0];
				dfs(1);
				sum+=cnt;
				leftSum=rightSum=cnt = 0; // 양쪽 추 무게합, cnt 초기화
			}while(np(input));
			System.out.printf("#%d %d%n",i,sum);
		}
	}
	
	private static void dfs(int n) {
	
		if(n == N && leftSum>=rightSum) { // 추가 모두 놓아졌다면
			cnt++;
			return;
		}
		if(leftSum>=rightSum+input[n]) { // 만약 오른쪽에 추를 놓을 수 있다면
			rightSum+=input[n]; // 오른쪽에 무게 추가
			dfs(n+1); // 다음 추 반복
			rightSum-=input[n]; // 오른쪽 추 제거
		}
		leftSum+=input[n]; // 왼쪽에 추 추가
		dfs(n+1); // 다음 추 반복
		leftSum-=input[n]; // 왼쪽 추 제거
	}
	
	//nextpermutation
	private static boolean np(int[] input) {
		int N = input.length-1;
		
		int i = N;
		while(i>0 && input[i-1]>= input[i]) --i;
		if(i == 0)
			return false;
		
		int j = N;
		while(input[i-1]>= input[j]) --j;
		swap(input,i-1,j);
		
		int k = N;
		while(i<k) swap(input,i++,k--);
		
		return true;
	}
	private static void swap(int[] input, int i, int j) {
		int temp = input[i];
		input[i] = input[j];
		input[j] = temp;
	}
}

 

✅ 후기

• 머리속으로는 어떻게 구현해야 하는지 생각은 났는데 코드로 쉽게 표현하려니 약간 힘들었다.
• 하지만 boolean을 이용하여 방문을 체크할 지, bismask를 이용할 지에 대해 고민을 다양하게 해봤는데 단순하게 1차원 적으로 푸는 방법을 택해서 풀었다.
• 시간을 더 줄이기 위해 위에 적어둔 방법들도 연습해봐야겠다.