[백준]_1174_줄어드는 숫자

2021.2.9 2021.3.1 Algorithm/Study3 301 2 mins

`브루트 포스 + 백트래킹

예시가 너무해서 찾다가 유사한 다른 문제를 찾았다

https://www.acmicpc.net/problem/1038

조합을 구했을 때 모든 수가 중복되지 않아 그것을 큰 순서로 나열했을 때 모두 줄어드는 숫자라 할 수 있다.
$_{n} \mathrm{C}_{0} + _{n} \mathrm{C}_{1} + … + _{n} \mathrm{C}_{n} = 2^n$ 이기 때문에 하나도 뽑지 않을 경우를 제외한 1023가지의 경우의 수 밖에 나올 수 없음.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


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

public class B18119 {
	static int N, M, cnt;
	static char[] idx = new char[2];
	static int[] bit;
	static int alpha = (1 << 27) - 1;
	/// 26개 1비트
	static String s;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		bit = new int[N];

		while (N-- > 0) {
			s = br.readLine();
			for (char c : s.toCharArray()) {
				bit[N] |= 1 << (c - 'a');
			}
			// 각 문자열 비트 생성
		}
		
		
		while(M-->0) {
			st = new StringTokenizer(br.readLine());
			char o = st.nextToken().charAt(0);
			char c = st.nextToken().charAt(0);
			// and/or 연산을 통해 비트를 켜고 끔
			if(o=='1') {
				alpha &= ~(1 << (c -'a'));
			}else {
				alpha |= (1<<(c -'a'));
			}
//			System.out.println(Integer.toBinaryString(alpha));
			cnt = 0;
			// 단어가 전부 있을 경우 연산 그대로 되는 듯
			for(int i : bit) {
				if((alpha & i) >= i) cnt++;
			}
			sb.append(cnt).append("\n");
		}
		
		System.out.println(sb);
	}

}

bit masking

int 는 32bit이기 때문에 알파벳 문제에 적용해볼 수 있다.

OR : 삽입
AND : 삭제
XOR : 삭제

Load Comments?