브루트포스 - 백준 1436번 영화감독 숌

IDEA 

맨 처음에는 일단 써봤다. 

1666

2666

3666

4666

5666

6660

6661

.........

규칙성을 찾을수가 없어서 666을 기준으로 앞에는 1 ~ 9를 더해주고 뒤로는 0~9를 더해줘서 리스트에 넣어준 후 

정렬을 통해 K번째 종말의 수를 찾아주면 되지 않을까? 생각을 해보았다. 

구현하기 귀찮을 거 같아서 다른 방법이 없을까 생각을 해보았다. 

우리가 찾는 수는 최대 10000번째 수이다. 그래서 완전탐색? 브루트포스를 이용해서 최소 666부터 숫자를 하나하나 늘려가며 6이 몇개인지 확인해도 주어진 시간 안에 돌아갈 거라고 생각했다. 

 

• while 반복문을 통해서 숫자를 하나하나 늘려가며 6이 연속으로 3개 이상 있는지 확인한다. 

6이 연속으로 3개 이상 있는 지 어떻게 확인하냐? 라는 것이다. 이렇게 숫자의 자리수 하나하나를 확인할때는 

문자열로 처리해 확인하는 것이 더 간편하다. 

 

• to_string을 이용해 문자열로 바꾼 후 string에서 제공하는 find를 사용하여 연속된 666이 존재하는 지 확인해준다. 

몇 번째 수인지를 나타내는 cnt를 이용하여 666이 존재하면 cnt를 카운트 해준 후 내가 원하는 번째 숫자라면 while문을 탈출한다. 

 

CODE

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

int main() {
	int m;
	scanf("%d", &m);
	int num = 666;
	int cnt = 0;
	while (1) {
		string str = to_string(num);
		if (str.find("666") != -1) cnt++;
		if (cnt == m) break;
		num++;
	}
	printf("%d", num);
}