백준 1436. 영화감독 숌

www.acmicpc.net/problem/1436

1436번: 영화감독 숌

주어지는 숫자 n이 10000이하의 자연수이기 때문에 브루트포스로 풀수있다.

 

666부터 숫자를 증가시키면서 숫자가 666을 포함하는지 검사하고 포함한다면 카운트를 증가시킨다.

카운트가 n이 될때의 숫자가 정답이다. 

 

#include <iostream>
using namespace std;

// 연속된 6이 3개 이상있으면 true 반환
bool sixs(long long n) {
    int six = 0;
    while(n) {
        if(six >= 3)
            return true;

        int last = n % 10; // 마지막자리 수
        if(last == 6) { // 마지막자리수가 6이 아니면
            six++;
        }
        else { // 마지막자리수가 6이면
            six = 0; // six 갯수 0으로 초기화
        }
        n = n / 10; // 마지막자리수 버림

    }

    if(six >= 3)
        return true;
    else
        return false;

}

int main() {
    int n;
    cin >> n;

    int cnt = 0;
    int i = 0;
    while(true) {
        if(sixs(i)) cnt++;

        if(cnt == n) {
            cout << i;
            return 0;
        }
        i++;
    }
}

실행시간 28ms.

 

 

아래는 string.find 함수를 이용해 숫자를 스트링으로 변환해서 답을 찾은것.

코드는 깔끔해진 반면 실행시간은 92ms로 늘어남.

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    int cnt = 0;
    int name = 666;
    string s;

    cin >> n;

    while(name) {
        // 현재 숫자를 스트링으로 변환후
        s = to_string(name);

        // 문자열에 "666"이 포함되어 있다
        if(s.find("666") != -1)
            cnt++; // 카운트 증가

        if(cnt == n) {
            cout << name << '\n';
            return 0;
        }
        name++;
    }

}

string.find() 함수는 파라미터로 전달된 문자열이 포함되있으면 시작지점을 반환.

없으면 string::npos 반환 (-1)