3671. 산업 스파이의 편지

문제링크

난이도	정답률(_%)
Gold IV	48.093%

메모리 (KB)	시간 (ms)
11888	144

설계

모든 경우를 dfs로 다 돌리면 아마 7!*6!*5!*4!*3!*2!*1! 125,411,328,000 번 반복될 것 같음.

일단 에라토스테네스의 체로 소수들을 모두 구해 놓는다.

확인해야할 숫자는 길이 1짜리, 2짜리, ... n 짜리 숫자들의 모든 순열이다.

두가지로 해봄.

next_permutation ( 21520kb, 480ms )

숫자를 next_permutation 으로 돌려서 1짜리, 2짜리 ... n 짜리 길이로 잘라서 에라토스테네스의 체에 걸리는지 확인한다. 여기서는 되든안되든 모든 순열을 만들어서 확인해 보기 때문에 느린것 같음.

do {
  for (int i = 0; i < size; i++) {
    string sub = s.substr(0, i + 1);
    int num = stoi(sub);
    if (visit[num]) continue;
    if (!che[num]) continue;
    visit[num] = true;
    ans++;
  }
} while (next_permutation(s.begin(), s.end()));

back tracking ( 11888kb 144ms )

여기서는 가지치기 되는 경우가 몇가지 있어서 모든 순열을 돌아보는 next_permutaion 보다는 반복 횟수가 적은가?

일단 순열 만들고 체크하는 방식이 반대임.

1번 방법은 순열을 만들고 1 ~ n 으로 잘라보기
2번 방법은 1 ~ n 짜리 순열을 만듬

음.. 시간차이가 나는 이유는 잘 모르겠음.

void bt(int maxLen, string& s, string& cur, set<int>& numSet) {
  if (cur.size() == maxLen) {
    int num = stoi(cur);
    if (numSet.find(num) != numSet.end()) return;
    if (che[num]) {
      numSet.insert(num);
      ans++;
    }
    return;
  }

  for (int i = 0; i < s.size(); i++) {
    if (selected[i]) continue;
    cur.push_back(s[i]);
    selected[i] = true;
    bt(maxLen, s, cur, numSet);
    cur.pop_back();
    selected[i] = false;
  }
}

for (int i = 1, size = s.size(); i <= size; i++) {
  bt(i, s, cur, numSet);
}

어떤 부분에서 두 알고리즘이 3배 넘게 속도차이가 나는 걸까요?

burning-carrot / study-problem-solving

[질문] junow obj 3671 산업 스파이의 편지 #127

3671. 산업 스파이의 편지

설계

시간복잡도