처음에 완전 탐색을 하면서 막대기가 생겨나는 경우의 수(있고 없고)마다 생겨나는 숫자를 M으로 나눠 지는지를 확인했다.
하지만 계속 틀리면서 다시 문제를보니 30만 자리라는 어마어마한 숫자 크기때문에 이렇게 풀면은 안되는 구나를 느꼇다.
결국 질문을 해서 힌트를 얻은결과 숫자 나누는 방법을 적용해서 풀면은 해결할 수 있다고 생각했다.
(나누기는 초딩때부터 아는건데...... 아주 세세하게 들어가서 나머지가 구해지는 과정을 그려보니 알 수 있었다.)
막대기 마다 생겨나는 부분이 M배수가 되는지 확인하면서(%M == 0) 막대기를 배치 시킬 수 있는 경우의 수를 구한다.
위에서 보면 막대기가 가능한 부분은 파란 부분인데, 여기서 생겨나는 왼쪽부분과 오른쪽부분이 M으로 나눠지는지 확인하면서 나눠지면 막대기가 존재할수 있는 수를 카운팅 해준다.
모든 개수를 세주고나서 최종적으로 구한 경우의 수에 -1을 해주면서 CASE 6의 막대기 생겨나는 경우의 수를 없애준다. 왜냐하면 이미 CASE1~5까지 CASE6에 해당하는 부분을 포함하기때문에 -1을 해주는 것이다. 즉, 2^구한 막대기 경우의수-1 을 하면 정답이 되게된다.
막대기때문에 생겨나는 숫자가 M으로 나눠지는지 확인하는 방법은 다음과 같다.
EX) 123456이 7로 나눠지는지 확인 하는 과정 - 우리는 보라색 부분의 식을 반복하면서 최종적으로 0인지 확인하면 된다.
소스코드)
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 | #include<cstdio> #include<iostream> using namespace std; int a[300000];//30만개 숫자 int N; int M; void solve(int t) { int before = 0; int mod = 0; int ret = 1; int cnt = 0; bool flag = false; for (int i = 0; i < N; i++) { mod = (10 * before) + a[i]; // 다음 숫자 생성 mod = mod % M; //숫자를 나눠본다. if (mod == 0) // 나눠지면 막대기 개수 증가 { cnt++; if (i == N - 1) flag = true; } before = mod; // 숫자 생성위해서 현재 나눈 나머지 값을 before로 넘겨준다. } if (!flag) { printf("#%d 0\n", t); return; } else { cnt--; for (int i = 0; i < cnt; i++) { ret = (ret * 2) % 1000000007; } printf("#%d %d\n", t, ret); } } int main() { int T; scanf("%d\n", &T); for (int i = 1; i <= T; i++) { scanf("%d %d", &N, &M); for (int i = 0; i < N; i++) { scanf("%1d", &a[i]); } solve(i); } return 0; } | cs |
반응형
'PS > SWEA' 카테고리의 다른 글
| 2007번 패턴 마디의 길이 (0) | 2018.10.16 |
|---|---|
| 1859번 백만 장자 프로젝트 (0) | 2018.10.13 |
| 5550번 나는 개구리로소이다 (0) | 2018.10.06 |
| 1926번 간단한 369게임 (0) | 2018.10.05 |
| 1868번 파핑파핑 지뢰찾기 (0) | 2018.09.30 |