[JAVA] [SWEA] 3234. 준환이의 양팔저울

준환이는 N개의 서로 다른 무게를 가진 무게 추와 양팔저울을 가지고 있다.

모든 무게 추를 양팔저울 위에 올리는 순서는 총 N!가지가 있고,

여기에 더해서 각 추를 양팔저울의 왼쪽에 올릴 것인지 오른쪽에 올릴 것인지를 정해야 해서 총 2N * N!가지의 경우가 있다.

하지만 양팔 저울에 갑자기 문제가 생겨서 무게 추를 올릴 때 오른쪽 위에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 커져서는 안 된다.
 
예를 들어 무게추가 총 3개, 무게가 각각 1, 2, 4 라고 하면 아래 그림처럼 총 15가지 경우가 나올 수 있다.

이런 방법으로 준환이가 양팔 저울에 모든 무게추를 올리는 방법은 총 몇 가지가 있을까?

 

이 문제의 경우 앞 문제에서 언급한 DFS에서 static field를 많이 언급할 경우 생기는 문제를 극명히 보여주는 문제이다.

 

사실 처음에 이게 왜 시간초과가 나는 것이고 문제가 되는지 이해를 잘 하지 못하였다.

 

왜냐하면 다른 사람이 푼 것을 보았을때 주어진 N개의 숫자를 먼저 순열로 구하고 \

 

그 후에 양팔저울에 올리는 시도를 하였었는데 그렇게 푸는 경우 시간초과가 나지 않고 안정적으로 해결 되었다.

 

하지만 같은 로직으로 두 로직을 합하여 정렬하면서 양팔저울에 올리는 시도를 하였는데 시간초과가 나서

 

고민을 많이 하였는데 이 때 static 으로 참조하던 변수들을 메소드의 인자값으로 넘겨주니

 

시간초과가 나지않고 통과가 되었다. 비록 시간초 자체는 후자가 느렸지만 좋은 것을 배운 문제였다.

 

1. 앞서 소개한 정렬 후 그 정렬한 무게추를 양팔 저울에 올리는 경우

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Solution {
	static int[] sinker;
	static int N;
	static int nSum;
	static boolean[] select;
	static int cnt;
	static int temp;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		String[] s = null;
		for(int t=1; t<=T; t++) {
			N = Integer.parseInt(br.readLine());
			sinker = new int[N];
			nSum = 0;
			select = new boolean[N];
			cnt = 0;
			s = br.readLine().split(" ");
			for(int i=0; i<N; i++) {
				sinker[i] = Integer.parseInt(s[i]);
			}
			permu(0);
			bw.write("#"+t+" "+cnt+"\n");
		}
		br.close();
		bw.close();
	}
	
	static void permu(int depth) {
		if(depth == N) {
			dfs(0,0,0);
			return;
		}
		for(int i=depth; i<N; i++) {
			temp = sinker[depth];
			sinker[depth] = sinker[i];
			sinker[i] = temp;
			permu(depth+1);
			temp = sinker[depth];
			sinker[depth] = sinker[i];
			sinker[i] = temp;
		}
	}
	
	
	static void dfs(int depth,int left, int right) {
		if(depth == N) {
			cnt++;
			return;
		}
		nSum = left+sinker[depth];
		dfs(depth+1, nSum, right);
		nSum = right+sinker[depth];
		if(nSum <=left) {
			dfs(depth+1, left, nSum);
		}
	}

}

 

2. 이 두가지를 합쳐서 푸는 경우

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Solution {
	static int[] sinker;
	static int N;
	static int nSum;
	static boolean[] select;
	static int cnt;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		String[] s = null;
		for(int t=1; t<=T; t++) {
			N = Integer.parseInt(br.readLine());
			sinker = new int[N];
			nSum = 0;
			select = new boolean[N];
			cnt = 0;
			s = br.readLine().split(" ");
			for(int i=0; i<N; i++) {
				sinker[i] = Integer.parseInt(s[i]);
			}
			dfs(0, 0, 0);
			bw.write("#"+t+" "+cnt+"\n");
		}
		br.close();
		bw.close();
	}
	
	static void dfs(int depth,int left, int right) {
		if(depth == N) {
			cnt++;
			return;
		}
		for(int i=0; i<sinker.length;i++) {
			if(select[i]) continue;
			
			select[i] = true;
			nSum = left + sinker[i];
			dfs(depth+1, nSum, right);
			nSum = right + sinker[i];
			if(nSum <= left) {
				dfs(depth+1, left, nSum);
			}
			select[i] = false;
		}
	}

}

 

이 코드의 경우 시간 초과가 난다. 하지만 다음에 나오는 3번은 시간초과가 나지 않는다.

 

3. 2번의 방식이지만 변수들을 static이 아닌 메소드 인자값으로 넘겨주는 경우

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Solution {
	static int cnt;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		String[] s = null;
		int N = 0;
		int[] sinker = null;
		boolean[] select = null;
		
		for(int t=1; t<=T; t++) {
			N = Integer.parseInt(br.readLine());
			sinker = new int[N];
			select = new boolean[N];
			cnt = 0;
			s = br.readLine().split(" ");
			for(int i=0; i<N; i++) {
				sinker[i] = Integer.parseInt(s[i]);
			}
			dfs2(0, sinker, 0, 0, 0, select);
			bw.write("#"+t+" "+cnt+"\n");
		}
		br.close();
		bw.close();
	}
	
	static void dfs2(int depth, int[] sinker, int nSum, int left, int right, boolean[] select) {
		if(depth == sinker.length) {
			cnt++;
			return;
		}
		for(int i=0; i<sinker.length; i++) {
			if(select[i]) continue;
			select[i] = true;
			dfs2(depth+1, sinker, nSum, left+sinker[i], right, select);
			nSum = right + sinker[i];
			if(nSum <= left) {
				dfs2(depth+1, sinker, nSum, left, nSum, select);
			}
			select[i] = false;
		}
		
	}
}

 

3번의 경우 잘 보면 cnt를 제외하고 다 메소드에 넣어준 것을 알 수 있다.