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

문제

• SWEA 3234
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

접근 방식은 크게 순열을 구한 후, 이 순열을 왼쪽에 넣는 경우와 오른쪽에 넣는 경우로 나누어 생각할 수 있다.
그래서 함수를 두개 만들 수 있지만 아래 코드는 합쳐진 코드이다. 그런데 의문인 것은 static변수로 선언했을 때는 시간초과가 나와서 테케 1개가 pass가 되지 않았다. 그래서 구글링한 후 local변수로 바꿔주니 통과했다. 아직 알쏭달쏭 한데 계속해서 주기적으로 풀어봐야할 문제이다.

• 풀이 동영상을 찾았는데 다음에 풀때는 영상을 참고하고 백지상태에서 다시 풀어보자.

코드

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 {

	static int Ans; // 정답: 경우의 수

	public static void main(String[] args) throws IOException {
		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++) {
			int N = Integer.parseInt(br.readLine()); //추의 개수 
			int[] weight = new int[N];
			Ans = 0;
			boolean[] visited = new boolean[N];

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				weight[i] = Integer.parseInt(st.nextToken());
			}

			calc(weight, 0, 0, 0, visited); // 계산 시작
			System.out.println("#" + tc + " " + Ans);
		}
	}

	//순열을 구하고 양팔저울에 올리는 시도를 한번에 합침 => static변수 사용하면 시간초과뜸
	private static void calc(int[] weight, int cnt, int left, int right, boolean[] visited) { // 뽑은 추 개수, 왼쪽 합, 오른쪽 합
		//N번 다 뽑았는지 확인하기 전에 얘가 첫 조건이어야함!!
		if (left < right) { // 지금 뽑은 추의 오른쪽이 왼쪽보다 크다면
			return; // 이 경우는 고려x
		}
		
		if (cnt == weight.length) { // N번 다 뽑았으면
			Ans++; //답을 하나 증가
			return;
		}

		for (int i = 0; i < weight.length; i++) {
			if (visited[i])
				continue; // 이미 뽑은 추라면 넘어감
			visited[i] = true; // 추를 선택해서
			calc(weight, cnt + 1, left + weight[i], right, visited); // 왼쪽에 넣는 방법
			//여기서 false를 하게 되면 왼쪽에 넣은 값을 오른쪽에서 또 넣을 수 있다.
			calc(weight, cnt + 1, left, right + weight[i], visited); // 오른쪽에 넣는 방법
			visited[i] = false;
		}
	}
}