Problem 1.4.6 Combination Lock - 2

처음 풀이 ( link )

---

문제 풀이

자물쇠 숫자 3개를 tuple<int, int, int>로 처리하고, 숫자 사이의 차이를 abs 이용해서 계산한다. 다만, modulo 연산에서 -를 지원하지 않기 때문에 dial number - 2 ( modulo -2) 보다 큰 경우도 고려한다. 3중 루프를 O(N^3)이지만 최대 dial number 100 을 생각하면, 속도에 문제가 될 것 같지는 않다. 필요하다면, key number 에서 5x5x5 로 가능한 숫자 배열을 작성하고, 그 배열 숫자들로만 루프를 돌리면 좀 더 빨라질 것 같다. 중복 제거를 위해서 set 에 무조건 입력하고, 중복이 제거된 결과의 수만 조회 했는데, 입력하기 전에 조회를 하고 없으면 입력하도록 하는것도 방법이 될 수는 있을 것 같다. 효율성은 find를 하고 없으면 입력하는것이 조금은 더 좋을 것 같다.

프로그램 내용

#define MAX_DIAL 100

/// tuple<int, int, int> key vs tuple<int, int, int> dest check
bool check_distance(tuple <int, int, int> key, tuple <int, int, int> dest, int dial_num);
{
    int a, b, c;
    int x, y, z;
    tie(a,b,c) = key;
    tie(x,y,z) = dest;
    int dist1, dist2, dist3;

    dist1 = abs(a-x);    dist2 = abs(b-y);    dist3 = abs(c-z);

    if ((dist1 <= 2 || dist1 >= dial_num-2)
        && (dist2 <= 2 || dist2 >= dial_num-2)
        && (dist3 <= 2 || dist3 >= dial_num-2) )
        return true;
    else
        return false;
}

int main() {
    /// Read requirement
    int dial_num = 0;
    fin >> dial_num;

    int f1, f2, f3;
    fin>> f1 >> f2 >> f3;

    int m1, m2, m3;
    fin>> m1 >> m2 >> m3;

    set <tuple<int,int,int>> c_codes;

    tuple <int, int, int> f_key = make_tuple(f1, f2, f3);
    tuple <int, int, int> m_key = make_tuple(m1, m2, m3);

    for(int id1=0;id1 < dial_num ; ++id1)
        for (int id2 = 0; id2 < dial_num; ++id2)
            for(int id3= 0; id3 < dial_num; ++id3)
                tuple <int, int, int> c_key = make_tuple(id1, id2, id3);
                /// check distance 1d1 with f1/m1, id2 with f2/m2, id3 with f3/m3
                if(check_distance(f_key, c_key, dial_num))
                    c_codes.insert(c_key);
                if(check_distance(m_key, c_key, dial_num))
                    c_codes.insert(c_key);

    if (dial_num < 6)
        fout << dial_num * dial_num * dial_num << endl;
    else
        fout << c_codes.size() << endl;

 

 

Chapter 1. Getting started (link)