Brute Force_1436

문제 출처: https://www.acmicpc.net/problem/1436

1436번: 영화감독 숌

666이 들어간 string을 찾는 '탐색' 알고리즘이다. 무작정 시도해보는 브루트포스(Brute Force) 방식으로 풀 수 있는 문제다. 자세히 알고리즘을 설명해보면,

 

숫자를 문자열로 하나씩 변환해가며 '666'이 들어갔다면 순서 번호를 하나씩 증가시키고, 입력받은 N과 순서 번호가 같아졌을 경우 해당 숫자를 return 하는 방식으로 구현할 수 있다.

 

주의할 것은, 666, 1666, 2666, 3666, 4666, 5666 다음에 6666이 아니라 6660 이라는 것이다. 문제의 난이도에 비해 정답비율이 45%로 낮은 것은 이 부분을 생각하지 못해 틀린 시도가 많다고 생각된다.

 

#include <iostream>
#include <string>

using namespace std;

int main() {

	int idxNumber = 665; // 영화제목 뒤에 붙을 숫자
	int N; // 순서 번호
	string strNumber; // idxNumber를 string으로 바꿨을 때 저장할 string 변수

	cin >> N; // 순서 번호 입력

	for (int cnt = 0;;) {
		idxNumber++; // 검사할 숫자를 하나 올린다.
		strNumber = to_string(idxNumber); // string으로 변환

		if (strNumber.find("666") != -1) { // 666이 있다면
			cnt++; // count 번호를 올리고
			if (cnt == N) { // 찾던 순서의 숫자라면
				cout << strNumber; // 출력하고 종료
				break;
			}
		}
	}
}