[1808번] 지희의 고장난 계산기

문제 출처 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yC3pqCegDFAUx

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

1. 고장난 계산기로 k이하의 값을 모두 만들어둔다.

2. k값이 a * b = k라면 a,b는 k의 약수이다.

3. 따라서 BFS를 통해 현재 값이 내가 만들어둔 값에 나누어떨어지면 그 수를 만들때 필요한 값 + 곱하기(1)을 더해준다.

4. 만약 현재 수가 내가 가지고있는 수와 같다면 그대로 넣어준다.

5. 최솟값을 도출한다.

소스 코드 : 

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 70 71 72 73 74 75 76 77 78 79 80 81 82

#include <iostream> #define MIN(a,b)(a < b ? a : b)   struct PAIR {     int first, second; }; struct NUM {     int num, cnt; }; int arr[10]; int k;   bool visit[1000002]; NUM number[1000002]; int nIdx;   PAIR q[1000002]; int first, last;   void init() {     nIdx = first = last = 0;     for (int i = 0; i < 1000002; i++)         visit[i] = false;     number[0] = { 0,1 }; } void makeNumber(int val, int cnt) {     if (val > k)         return;     if (val <= k)         number[nIdx++] = { val, cnt };       for (int i = 0; i < 10; i++) {         if (arr[i]) {             if(!(i == 0 && val == 0))                 makeNumber(val * 10 + i, cnt + 1);         }     } } int main() {     freopen("input.txt", "r", stdin);     int tCase;     scanf("%d", &tCase);       for (int tc = 1; tc <= tCase; tc++) {         init();           for(int i = 0 ; i < 10; i ++)             scanf("%d", &arr[i]);         scanf("%d", &k);           makeNumber(0, 0);         q[last++] = { k,0 };           bool chk = false;         int ans = 987654321;         while (first < last) {             int here = q[first].first;             int cnt = q[first++].second;               if (here == 1 && cnt) {                 chk = true;                 ans = MIN(ans, cnt + 1);             }             if (visit[here])                 continue;               visit[here] = true;             for (int i = 1; i < nIdx; i++) {                 if (here < number[i].num)                     continue;                 if (here % number[i].num == 0)                     q[last++] = { here / number[i].num, cnt + number[i].cnt + 1 };                 if(here == number[i].num)                     q[last++] = { 1, cnt + number[i].cnt };             }         }           printf("#%d %d\n",tc,  chk ? ans : -1);       }     return 0; } Colored by Color Scripter

cs