이 문제는 666이 들어가는 수 중에서 n 번째로 작은 수를 찾는 문제이다.

처음에 조합,순열 이런 느낌으로도 풀어보려했으나, 잘 떠오르지 않았다.

이 문제를 잘보면 N<=10000 이다. 따라서 내가 찾는 수는 아무리 커도 6660000 안에서 전부 해결된다.

이정도 수면 1부터 6660000까지 모든 수를 순회하며 666을 포함하는지 확인해봐도 시간복잡도 측면에서 문제가 없을듯보인다.

이런 문제는 무식하게 풀어야한다.

1. 풀이

#include <bits/stdc++.h>

using namespace std;

int main() {
    int cnt;
    cin >> cnt;
    int i;
    for(i=0;i<6660000; i++) { //O(6660000*3*S)
        if(to_string(i).find("666") != string::npos) cnt--;
        if(cnt==0) break;
    }
    cout << i;
    
    
    return 0;
}

시간복잡도는 최악의 경우 O(666000003S)인데 S(to_string()으로 문자열로 바꾼 숫자의 길이)는 매 반복마다 변한다.

그러나 S=7로 둬도 1.2억이므로,,실제 연산량은 1억 이하일 것으로 보인다. (만약 시간초과 뜨면 다른 방법으로 풀이하면된다. 연산량이 1억 이하일 것으로 보이거나, 간당간당해보이는 경우라면 충분히 시도할만한 가치가있다)

아마 제출하면 시간 초과가 뜨지않을 것이다.

2. 오답 노트

(1) 범위는 파악했지만 전부 순회할 생각을 못했다

문제를 보고 내가 찾는 수는 아무리 커도 6660000 안에서 전부 해결됨은 파악했지만, 얘를 전부 순회할 생각을 하지못했다.

최대가6660000 정도의 수라면 모든 수를 순회하는것이 충분히 가능하다. 다음 부터는 모든 수를 순회하며 찾는것이 가능한지를 가장 먼저 떠올려야겠다.

무식한 풀이가 최고로좋다. 다른 고차원적인 풀이를 찾기전에 무식하게 가능한 범위를 전부 순회하면서 찾는 풀이를 가장 먼저 떠올려야한다.

사고 순서 : 가능한 범위 전부 순회하면서 찾기 -> 안되면, 다른 풀이 생각해보기