[백준] 20209 스트레이트 스위치 게임 (부분집합)

1. 문제

www.acmicpc.net/problem/20209

20209번: 스트레이트 스위치 게임

2. 접근방법

전에 올렸던 포스팅

lovelyunsh.tistory.com/77

[백준] 20209 스트레이트 스위치 게임

저때는 bfs를 이용했는데

부분집합을 이용하는 방법도 있어 추가 한다.

 

우선 착안되는 아이디어는

 

몇번 스위치든 5번 누르면 맨 처음 상태로 돌아온다는 점에서

누르는 횟수를 제한 시킬수 있다는 것이다.

 

이유는

스위치를 누르고 4이상인 숫자가 되면 다시 0으로 되기 때문에 %5연산을 하는데

이때 5번을 누르면 (X + a * 5 )%5 가 되어 언제나 X가 다시 나오게 된다.

 

이것을 이용해 스위치 누르는 횟수를 5미만으로 한정하고

누를 수 있는 모든 부분집합을 구해서 풀이하면 된다.

 

즉 스위치를 누를 수 있는 최대 횟수는 스위치 갯수 * 4로 한정한다. 

나머진 이전과 같은 개념으로 구현만 해주면 된다.

 

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class G3_20209스트레이트스위치게임부분 {
	static int firstCube[], N, K;
	static ArrayList<Integer> switchs[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		firstCube = new int[N];
		switchs = new ArrayList[K];
		sel = new int[K];
		for (int i = 0; i < K; i++)
			switchs[i] = new ArrayList<Integer>();
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			firstCube[i] = Integer.parseInt(st.nextToken());
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int k = Integer.parseInt(st.nextToken());
			for (int j = 0; j < k; j++)
				switchs[i].add(Integer.parseInt(st.nextToken()) - 1);
		}

		powerset(0, K * 4);
		// 부분 집합 으로 스위치 누르는 횟수들을 만들고
		// 그 숫자 만큼 스위치 눌러보고
		// 숫자가 같아졌는지 검사하기
		if(!finish)
			ans = -1;
		System.out.println(ans);
	}

	static int sel[], ans = Integer.MAX_VALUE;
	static boolean finish;
	static void powerset(int selidx, int num) {
		if (selidx == K) {
			if(!check(click()))
				return;
			int sum = 0 ;
			for(int i = 0 ; i < K ; i++)
				sum += sel[i];
			ans = Math.min(ans, sum);
			return;
		}
		for (int i = 0; i <= num; i++) {
			if (i > 4)
				break;
			sel[selidx] = i;
			powerset(selidx + 1, num - i);

		}
	}

	static int[] click() {
		int newcube[] = firstCube.clone();
	
		for (int i = 0; i < K; i++) {
			if (sel[i] == 0)
				continue;
			for (int j : switchs[i])
				newcube[j] = (newcube[j] + (i+1) * sel[i]) % 5;
		}
		return newcube;
	}
	static boolean check(int [] cube) {
		int flag = cube[0];
		for (int i = 1; i < N; i++) {
			if (cube[i] != flag)
				return false;
		}
		finish = true;
		return true;
	}

}

4. 마치며

이게 bfs로 푼거고

이게 부분집합으로 푼것.

bfs는 최소거리를 바로 찾아가니

모든 경우의 수를 비교하는 부분집합보다 빨라야 할 것 같은데 부분집합이 훨씬 더 빠르게 나왔다

흠...... 이유를 좀 더 고민해봐야겠다.