[브루트포스] 백준 1107 C++ / 또 무수한 틀림과

하 또 막혔다 또

#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

int N, M;
int *broken;

int calMin(int num)
{
    // 1. 100에서 +, -해서 움직이는 횟수
    int fromHundred = abs(100-num);

    //2. 앞자릿수부터 고장난 숫자 있는지 검사
    string cp = to_string(num);
    for(int i=0; i<cp.size(); i++)
    {
        int tmp = cp[i] - '0';
        for(int j=0; j<M; j++)
        {
            if(tmp == broken[j])
                while(cp[i] != broken[j])
                    tmp++;
        }
    }
}

int main()
{
    cin >> N >> M;

    broken = new int[M];
    for(int i=0; i<M; i++)
        cin >> broken[i];

    // N이 100이면 0 출력
    if(N == 100)
    {
        cout << 0 << endl;
    }
    // M이 0이면 N의 자릿수 구해서 출력
    else if(M == 0)
    {
        string n = to_string(N);
        cout << n.size() << endl;
    }
    else{
        cout << calMin(N) << endl;
    }

    return 0;
}

 

- 100이면 0 출력,

- 고장난 버튼 개수가 0이면 자릿수 구해서 출력

- 그 외의 경우는 100에서 플러스 마이너스 해주는 경우랑 아닌 경우 중 최솟값을 구해줘야 하는데

 

2번 방법이 너무 복잡해질 것 같단 말이지

---

브루트 포스

브루트 포스(brute force), 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법 (출처: 나무위키)

 

 

2번 풀이 방법

=> 0부터 고장난 숫자 있는지 확인, 

최악의 경우 100에서 500000까지 +해야 할 수도 있음

---

• 4% 틀렸습니다 - 제출 코드

#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

int N, M;
int *broken;

bool is(int num)
{
    string cp = to_string(num);
    for(int i=0; i<cp.size(); i++)
    {
        int tmp = cp[i] - '0';
        for(int j=0; j<M; j++)
        {
            if(tmp == broken[j])
                return false;
        }
    }
    return true;
}

int main()
{
    cin >> N >> M;

    broken = new int[M];
    for(int i=0; i<M; i++)
        cin >> broken[i];

    int res;
    string strN = to_string(N);
    int sz = strN.size();

    // N이 100이면 0 출력
    if(N == 100)
    {
        res = 0;
    }
    // M이 0이면 N의 자릿수 구해서 출력
    else if(M == 0)
    {
        res = sz;
    }
    else{
        // 1. 100에서 +, -해서 움직이는 횟수
        int fir = abs(100-N);

        //2. 
        for(int i=0; i<1000000; i++)
            if(is(i))
            {
                int sec = abs(N-i)+sz;
                fir = min(fir, sec);
            }

        res = fir;
    }

    cout << res << endl;
    return 0;
}

 

으 화나

• 수정 사항 / 질문게시판의 반례 모음을 활용했음

1. M이 0일때 숫자 크기를 반환해주면 안됨

101

0

 

입력이 저렇게 들어올 경우 100에서 + 한번 눌러주는 게 더 작기 때문에 출력값이 1이 나와야 하는데 3이 나와버림

 

2.  숫자 크기 비교할 때

 

        for(int i=0; i<1000000; i++)
            if(is(i))
            {
                int sec = abs(N-i)+sz; // sz는 입력받은 N의 자릿수
                fir = min(fir, sec);
            }

 

숫자 자릿수를 저렇게 더해주면 

 

1555
8
0 1 3 4 5 6 7 9

 

입력이 저렇게 들어올 때 888에서 +를 667번 눌러 출력값이 670이 나와야 맞는데

1555의 자릿수인 4를 더하면 출력값이 671이 나와버림

 

• 정답 코드

#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

int N, M;
int broken[10] = {0, };

bool is(int num)
{
    string cp = to_string(num);
    for(int i=0; i<cp.size(); i++)
    {
        int tmp = cp[i] - '0';
        if(broken[tmp] == 1)
            return false;
    }
    return true;
}

int main()
{
    cin >> N >> M;

    for(int i=0; i<M; i++)
    {
        int input;
        cin >> input;
        broken[input] = 1;
    }
        
    int res;
    string strN = to_string(N);
    int sz = strN.size();

    // N이 100이면 0 출력
    if(N == 100)
    {
        res = 0;
    }
    else{
        // 1. 100에서 +, -해서 움직이는 횟수
        int fir = abs(100-N);

        //2. 
        for(int i=0; i<=1000000; i++)
            if(is(i))
            {
                int sec = abs(N-i)+to_string(i).length();
                fir = min(fir, sec);
            }

        res = fir;
    }

    cout << res << endl;
    return 0;
}