<Algorithm> 132. 동아리실 관리하기(SWExpert)
by BFine반응형
동아리실 관리하기(SWExpert)
- 비트마스크 & 시뮬레이션 문제
- 처음에 접근을 수학문제인 줄 알고 수식으로 풀려고 했는데 풀수가 없어서 힌트를 보니 시뮬레이션이였다.
- 시뮬레이션이란 것을 알았음에도 머리속으로 그려지지 않아서 다른 답안을 참고해서 풀었다.
- 가장 중요한 건 A가 첫번째 열쇠를 가진 것이고 그에 따라 모든 경우의 수를 탐색해야 했다.
- 한 곳에 머무르지 않고 다각도로 접근할 수 있는 능력이 되게 중요하다는 것을 느꼈다.
|
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
import java.util.Scanner;
public class Solution {
public static int[][] res;
public static int ans;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
/******************************
* 비트마스크를 이용해 방장과 전날에 있던
* 사람들을 파악하고 이전 방의 사람들이
* 키를 가질 수 있는 모든 경우를 탐색하여
* 경우의 수를 구한다.
*
* A -> A ->
* AB->
*
* AB -> A ->
* ~~
* -> B ->
* ~~
* -> AB ->
* ~~
*******************************/
for(int t = 1; t <= T; t++) {
String masters = sc.next();
res = new int[masters.length()][16];
ans = 0;
sol(masters);
System.out.println("#"+t+" "+ans);
}
}
public static void sol(String masters) {
for(int k = 0; k < masters.length(); k++) {
int master = 1 << (masters.charAt(k) - 'A');
for(int i = 1; i < 16; i ++) {
if(k == 0) {// 첫날
if((i&master)!=0 && (i&1)!=0) {
res[k][i] = 1;
}
}else {
if(res[k-1][i] != 0) {// 두번째 날부터
for(int j = 1; j < 16;j++) {
if((i&j)!=0 && (j&master)!=0) {
res[k][j] =(res[k][j] + res[k-1][i]) % 1000000007;
// 모든경우의 수를 앞쪽으로 누적
}
}
}
}
}
}
for(int i = 1; i < 16; ++i) {
ans =(ans+res[masters.length()-1][i]) % 1000000007;
}
}
}
|
|
|
cs |
참고 & 출처
반응형
'공부(2018~2019) - 스킨변경전 > Algorithm' 카테고리의 다른 글
| <Algorithm> 134. 아기상어(BJO) (0) | 2019.03.17 |
|---|---|
| <Algorithm> 133. 동철이의 일분배(SWExpert) (0) | 2019.03.15 |
| <Algorithm> 131. 최대상금(SWExpert) (0) | 2019.03.11 |
| <Algorithm> 130. 하나로(SWExpert) (0) | 2019.03.09 |
| <Algorithm> 129. 장훈이의 높은 선반(SWExpert) (0) | 2019.03.08 |
블로그의 정보
57개월 BackEnd
BFine