[Algorithm]Boj 1436

1436

• 숫자 안에 "666"이 포함되어있는 수 중에 작은것부터 N 번째에 있는 수를 출력하는 문제이다.

  • 666이 연속으로 포함되어있는 수를 이하 종말의 숫자라고 하자.

• 666, 1666, 2666, 3666, 4666, 5666, 6661, 6662, 6663 ... 이러한 순으로 나아갈 것이다.

• 따라서, index가 작은것 부터 순차적으로 올라가면서

• 종말의 숫자인지 체크하면 된다.

• 체크하는 방식에는 두 가지가 있는데,

  • 숫자를 문자열로 바꾼후 인덱스가 세 개 연속 '6'이면 종말의 숫자
  • 맨 뒷자리를 하나씩 지워가면서 0이될때까지 반복, 1000의 나머지가 666이면 종말의 숫자
    • 만약 234666123 이라는 숫자가 있다고 하자
    • 234666123 % 1000 = 123 이므로 다음으로
    • 23466612 % 1000 = 612 이므로 다음으로
    • 2346661 % 1000 = 661 이므로 다음으로
    • 234666 % 1000 = 666 이므로 체크완료 !
  • 이렇게 연속적으로 어떠한 숫자가 포함되어있는지 체크하는 간편한 방법은 하나씩 지우면서 확인하면 된다.

• 문자열로 체크하는 방식 → vector를 사용해 배열화 했다.

• 반복문을 1000000000 (10억) 까지 돌려보고 N이 10000일 때 몇이 나오는지 보고 코드를 수정했다.

  • 개 무식한 방법

• 이는 쓸데없는 자원낭비 및 N이 많이 커질경우 (문제에서 10000으로 제한을 뒀지만..) 처리할 수 없다.

  #include <iostream>
  #include <vector>
  
  using namespace std;
  
  int check(string str)
  {
  	for (int i = 0; i < str.size() - 2; i++)
  	{
  		if (str[i] == '6' && str[i + 1] == '6' &&
  				str[i + 2] == '6')
  			return (1);
  	}
  	return (0);
  }
  
  vector<int> make_str(void)
  {
  	string temp;
  	vector<int> v;
  	for (int i = 666; i < 3666066; i++)
  	{
  		temp = to_string(i);
  		if (check(temp))
  			v.push_back(i);
  	}
  	return (v);
  }
  
  int main(void)
  {
  	vector<int> a;
  
  	int N;
  	cin >> N;
  	a = make_str();
  	cout << a[N -1 ] <<endl;
  }

• 숫자로 체크하는 방법
  - 나에게 비교적 신선하게 다가왔다. 기억해두고 나중에 써먹자.

  #include <iostream>
  
  using namespace std;
  
  int main(void)
  {
  	int N;
  
  	cin >> N;
  	int count = 1;
  	int cur= 666;
  	// count가 N이 될 때까지
  	while (count != N)
  	{
  		cur++;
  		//원본 cur는 수정되면 안되기때문에 복제
  		int temp = cur;
  		// temp가 0이될 때 까지
  		while (temp)
  		{
  			// 맨뒷자리 세 자리가 666이면
  			if (temp % 1000 == 666)
  			{
  				// count 를 하나 증가시켜주고 break를 건다.
  				// 여기서 break를 걸지 않으면
  				// 6666666 에서 count를 최대 5번까지 증가시켜버릴 수도 있으니 주의
  				// 666666
  				// 66666
  				// 6666
  				// 666
  				count++;
  				break;
  			}
  			//한자리씩 지움
  			temp /= 10; 
  		}
  	}
  	cout << cur;
  }