[BruteForce] BOJ1436: 영화감독 숌

1436번: 영화감독 숌 (acmicpc.net)

1436번: 영화감독 숌

 

입력 N은 10000보다 작은 자연수이고, 문제에서 제시하는 "종말의 수"는 최소한 1000개에 1개 이상씩은 존재한다. 666이 가장 작은 종말의 수이기 때문에 xxxx~~ + 666 형태인 수는 역시 종말의 수가 되기 때문이다. 따라서 최악으로 치닫더라도 10000*1000으로 1억보다 적기 때문에 그냥 순수하게 0부터 하나씩 키워 가면서 N 번째 종말의 수가 무엇인지 찾아 보기로 하였다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> doomNumbers;
bool isDoomNumber(int test)
{
    bool result = false;
    int repeatedSixNum = 0;
    while (test != 0)
    {
        if (test % 10 == 6)
        {
            repeatedSixNum++;
            if (repeatedSixNum >= 3)
            {
                result = true;
            }
        }
        else
        {
            repeatedSixNum = 0;
        }

        test /= 10;
    }
    return result;
}

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

    int doomNumberCnt = 0;
    int currentNum = 0;
    while (true)
    {
        if (isDoomNumber(currentNum))
        {
            //cout << "doomNumber: " << currentNum << "\n";
            doomNumberCnt++;
            if (doomNumberCnt == N)
            {
                break;
            }
        }
        currentNum++;
    }
    cout << currentNum;
}

기본적인 코드기 때문에 풀이에 대해 따로 첨언할 부분은 없겠지만, 문제를 풀면서 이 문제가 '브루트포스' 카테고리에 있지 않고 일반 코테나 프로젝트 중에 만났다면 어땠을까 하는 생각이 들었다. 그때도 "대충 최악의 경우에도 경우의 수가 몇 개 아래로 떨어질 것 같으니까 그냥 하나하나 돌려보며 찾아야겠다"는 생각을 했을까? 아마 안 그랬을 것 같다. 솔직히 경우의 수가 1억개 이하면 그냥 브루트포스를 돌려도 무방하다는 것도 학교 스터디에서 잘 하는 친구가 말해준 대로 앵무새처럼 읊는 것이지 나도 왜 그런지 정확히 모른다. 하면 할수록 부족하다는 것만 깨닫게 된다.