본인 풀이 (7/5)

#include<bits/stdc++.h>
using namespace std;
int n;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    // 18진수
    // 1a 2a 3a 4a 5a 6a 7a 8a 9a
    // a 1a 2a 3a.. 5a a0, a1, a2, a3, a4, a5, a6 a7, a8, a9, 7a, 8a, 9a
    if(n==1){
        cout << 666 << "\n";
    }else{
        int ret = 0;
        // 10의자리
        int pre = (n - 1) / 19;
        ret += pre * 10000;

        // a 위치
        int suf = (n - 1) % 19;

        if(suf == 0){
            cout << ret + 666 << "\n";
        }else if((suf >= 1 && suf <= 5)){
            cout << ret + 666 + 1000 * suf << "\n";
        }else if(suf > 15 && suf < 20){
            cout << ret + 666 + 1000 * (suf - 9) << "\n";
        } else {
            cout << ret + 10 * 666 + (suf - 6) % 10 << "\n";
        }
    }

    return 0;
}

1. 풀이 실패했음
2. 666을 같은 문자로 보고 0a, 1a ... 9a까지 순회하는데, 6a가 있는 경우 a6이 더 작은 수이므로 십의자리가 올라가는 기준을 18진수로 놓고 풀이해보았다.
3. 중간에 6이 하나 더 추가되는 66a는 6a6, a66들을 고려해야 하나 싶긴 한데.. 반례 찾기가 너무 귀찮고 시간 아까워서 포기했음

모범 답안

강의에서는 무식하게 풀라고 하는데 어떤게 무식한 풀이일지 선택하는건?

#include<bits/stdc++.h>
using namespace std;
int n;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    int i = 666;

    for (;; i++){
        if(to_string(i).find("666") != string::npos){
            n--;
        }
        if (n == 0){
            break;
        }
    }
    cout << i << "\n";

    return 0;
}

1. 진짜 무식하다 - 그냥 시작지점 666부터 하나씩 순회하면 됨 667, 668... 각 숫자 안에 666이라는 숫자가 포함되어 있는지 확인하면 됨
2. n이라는 숫자가 10000 이하이니까.. 6660 6661 ... 6660000까지 순회하게 된다. int 범위는 –2,147,483,648 ~ 2,147,483,647 이고 연산의 수가 대략 1천만 아래이면 (문제따라 다름) 무식하게 돌려볼만한 문제가 된다.

복습 (7/12)

#include<bits/stdc++.h>
using namespace std;
int n;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int start = 666;
    string ret;
    cin >> n;

    while(n > 0){
        string s = to_string(start);
        int cnt = 0;
        for(char c : s){
            if(c - '0' == 6){
                cnt++;
            }
        }
        if(cnt >= 3){
            ret = s;
            n--;
        }
        start++;
    }
    cout << ret << "\n";
    return 0;
}

1. 틀렸음
2. 문자열 666을 찾는게 아니라 666, 667 ~ 9999까지 문자열화 하여 한 자리수마다 6이 나오면 카운트를 + 하였음.
3. 그렇게하면 안되는게, 6066을 정답으로 처리하여 n을 하나 빼줘버린다.
4. 6이 연속으로 세개 등장해야한다는 조건을 꼼꼼히 체크하자

재풀이

#include<bits/stdc++.h>
using namespace std;
int n;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int start = 666;
    string ret;
    cin >> n;

    while(n > 0){
        string s = to_string(start);
        if(s.find("666") != string::npos){
            ret = s;
            n--;
        }
        start++;
    }
    cout << ret << "\n";
    return 0;
}