[SWEA-3234][백트래킹] 준환이의 양팔저울 - Java

백트래킹 문제입니다. 문제의 제한 사항에 맞게 안되는 경우는 걍 안가면 됩니다.

시간이 빡빡하게 매겨집니다. 그래서 별짓 다해봤습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Solution {
	int N;
	int ans;
	
	void dfs(int cnt, int[] w, boolean[] v, int l, int r) {
		if(cnt == N) {
			ans++;
			return;
		}
		
		for(int i = 0 ; i < N; i++) {
			if(v[i]) continue; 
			v[i] = true;
			if(l >= r + w[i]) {
				dfs(cnt+1, w, v, l, r + w[i]);
			}
			dfs(cnt+1, w, v, l+w[i], r);
			v[i] = false;
		}
	}
	
	public static void main(String[] args) throws IOException {
		Solution s = new Solution();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 1; tc <= T; tc++) {
			s.N = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine(), " ");
			int[] weights = new int[s.N];
			boolean[] v = new boolean[s.N];
			int left = 0, right = 0;
			
			for(int i = 0; i < s.N; i++) {
				weights[i] = Integer.parseInt(st.nextToken());
			}
			s.dfs(0, weights, v, left, right);
			bw.write("#" + tc + " " + s.ans + "\n");
			s.ans = 0;
		}
		bw.flush();
		bw.close();
	}
}

 

우선 넣으면서 체크해줘야 하기 때문에 순열을 만들면서 진행합니다.

갖고 올 수 있는 무게 추를 먼저 찾고,

1. 오른쪽에 놔둬도 왼쪽의 무게보다 크지 않다면 dfs 를 쭉 진행해줍니다.
2. 왼쪽에 두고 dfs를 진행합니다.

 

이렇게 하고 N개를 모두 저울에 올렸을 때 ans++ 해주면 됩니다.

 

맨첨에 StringBuilder를 썼는데 시간초과 떠서 바로바로 출력하니까 21개 중에 20개 맞췄슴니다..

Solution 객체 생성하고 static 변수 다 뺐는데도 계속 한 개가 틀렸다고 떠서 결국 BufferedWriter 써서 통과됐습니당.. ^^;

 

 

감사함니다 ㅎ.ㅎ