1107 리모컨 [미완]

계속 맞왜틀했던 문제

 

맞는 거 같은데 어디가 문제지?? 싶었는데 순열을 문자열 길이만큼 확인해서 문제였다.

 

1부터 500000까지 확인해야했다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int num;
int minv = 1000000;

void pick(int m, vector<int>& picked, int now, vector<int> v)
{
    if (now == m)
    {
        string tmp = "";
        for (int i = 0; i < picked.size(); i++)
            tmp += picked[i] + '0';
        if (abs(num - stoi(tmp)) < abs(num - minv))
            minv = stoi(tmp);
        return;
    }

    for (int next = 0; next < v.size(); ++next)
    {
        picked.push_back(v[next]);
        pick(m, picked, now + 1, v);
        picked.pop_back();
    }
}

int     main()
{
    int m;
    cin >> num;
    cin >> m;

    vector<int>v(10);
    for (int i = 0; i < 10; i++)
        v[i] = i;

    for (int i = 0; i < m; i++)
    {
        int r;
        cin >> r;
        v.erase(find(v.begin(), v.end(), r));
    }
    
    string str = to_string(num);
    vector<int> picked;
    pick(str.size(), picked, 0, v);

    str = to_string(minv);
    int ans = min((unsigned int)(str.size() + abs(num - minv)), (unsigned int)abs(num - 100));
    cout << ans << endl;

    return 0;
}

 

그 다음으로 든 생각이 누룰 수 있는 버튼을 모두 누르는 경우는 전에 공부했던 부분집합 비트마스크로 표현하는 걸로 해결가능하지 않나?? 싶었음

 

하지만 다 짜고 알았다... 이런 경우는 5555처럼 같은 숫자 연속으로 못 누른다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int num;
int minv = 1000000;

void pick(vector<int>& v)
{
    for (int i = 1; i < (1 << v.size()); i++)
    {
        string tmp = "";
        for (int j = 0; j < v.size(); j++)
        {
            if (i & (1<<j))
                tmp += v[j] + '0';
        }
        if (abs(num - stoi(tmp)) < abs(num - minv))
            minv = stoi(tmp);
    }
}

int     main()
{
    int m;
    cin >> num;
    cin >> m;

    vector<int>v(10);
    for (int i = 0; i < 10; i++)
        v[i] = i;

    for (int i = 0; i < m; i++)
    {
        int r;
        cin >> r;
        v.erase(find(v.begin(), v.end(), r));
    }
    
    pick(v);

    cout << minv << endl;

    string str = to_string(minv);
    int ans = min((unsigned int)(str.size() + abs(num - minv)), (unsigned int)abs(num - 100));
    cout << ans << endl;

    return 0;
}

 

좀더 고민해봐야겠음

 

---

아 이거 순열 구할 때 길이가 m일 때 확인하게 했는데 그런거 없이 함수 호출할 때마다  확인해줌

 

코드는 이렇다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int num;
int minv = 1000000;

void pick(vector<int>& picked, int now, vector<int> v)
{
    if (now == 7)
        return ;
    if (picked.size() != 0)
    {
        string tmp = "";
        for (int i = 0; i < picked.size(); i++)
            tmp += picked[i] + '0';
        if (abs(num - stoi(tmp)) < abs(num - minv))
            minv = stoi(tmp);
    }

    for (int next = 0; next < v.size(); ++next)
    {
        picked.push_back(v[next]);
        pick(picked, now + 1, v);
        picked.pop_back();
    }
}

int     main()
{
    int m;
    cin >> num;
    cin >> m;

    vector<int>v(10);
    for (int i = 0; i < 10; i++)
        v[i] = i;

    for (int i = 0; i < m; i++)
    {
        int r;
        cin >> r;
        v.erase(find(v.begin(), v.end(), r));
    }

    string str = to_string(num);
    vector<int> picked;
    pick(picked, 0, v);

    str = to_string(minv);
    int ans = min((unsigned int)(str.size() + abs(num - minv)), (unsigned int)abs(num - 100));
    cout << ans << endl;

    return 0;
}

 

pick().size가 0이면 아직 숫자가 없는 거니깐 패스하고

 

이 다음부터 숫자가 하나 들어올테니깐 숫자 비교를 한다

 

now가 7이 되면 숫자가 7자리라는 거고 50만을 벗어났다는 뜻이므로 종료함

 

근데 틀림ㅋㅋㅋ 

 

잘 모르겠다 내일 또보자구 친구