백준 1436 영화감독 숌

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

 

서론

아이디어는 간단했지만, 구현 실수로 반례찾는데 시간 다 보낸 문제.

반례는 66066이 출력되는 문제가 발생.

원인은 6이 연속으로 3개 이상 포함되는지 확인하기 위한 코드에서 문제가 있었다.

 

아이디어

브루트포스 문제.

1부터 아주 큰 수까지 6이 연속으로 3번 들어가는지 확인하는 코드에 전부 집어넣는다.

6이 연속으로 3번 이상 들어가는지 확인하는 코드는

-

들어온 숫자의 자릿수를 분해

각 자리가 6이고 이전 자릿수도 6이면 카운트 증가

카운트가 2 이상이면 6이 3개이상이므로 true

-

 

구현

34번째 줄 2666799는 n이 10000일때의 수

//c++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;

// 반례 : 66066

bool numSix(int input) {
	int cur = 0;
	int prev = 0;
	int cnt = 0;
	while (1) {
		if (input == 0) break;
		prev = cur;
		cur = input % 10;
		input /= 10;
		if (cur == 6 && prev == cur) { 
			cnt++;
			if (cnt >= 2) return true;
		}
		else cnt = 0;
	}
	return false;
}

int main() {
	vector<int>v;
	cin >> n;
	for (int i = 1; i <= 2666799; i++) {
		if (numSix(i) == true) v.push_back(i);
	}
	cout << v[n - 1];
	//for (int i = 0; i < n; i++) cout << v[i] << endl;
}