[백준] 1436번 영화감독 숌 (C)

문제 주소

백준 1436번 영화감독 숌

알고리즘

브루트 포스

힌트

7번째 짜리에서 6이 연속으로 3번 이상 나오는 경우가 10000번이 넘는다. (9*9*9*9*5)

문제 풀이

n의 범위가 10000 이하이기 때문에 1부터 1씩 증가 시키면서 n번째의 수를 찾아도 제한 시간안에 풀 수 있다. count6 함수는 6이 연속된 개수를 확인하는 함수이다.

#include<iostream>
using namespace std;
int count6(int i){
    int cnt=0,flag=0;
    while(i>1){
        if(i%10==6){
            if(!flag)
                flag=1;
            cnt++;
        }
        else if(flag){
            if(cnt>=3)
                return cnt;
            flag=0;
            cnt=0;
        }

        i/=10;
    }
    return cnt;
}
int main(){
    int n,cnt=0,i=0;
    cin>>n;
    while(1){
        i++;
        if(count6(i)>=3)
            cnt++;
        if(cnt==n)
            break;
    }
    cout<<i;
}

[백준] 1436번 영화감독 숌 (C)