[Baekjoon] 1436번: 영화감독 숌

 

 

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

1436번: 영화감독 숌

 

---

 

문제 해결 과정

착안

$N$ 번째 종말의 수를 찾을 때까지 반복문을 통해 666부터 시작하여, 숫자를 문자열로 바꾸었을 때 666이라는 문자열을 포함하는지의 여부를 확인하여 카운팅하고 숫자를 1씩 증가시킨다(브루트 포스(brute-force) 방법).

 

또는, $N (1 \le N \le 10000)$ 번째 종말의 수가 가지는 규칙성을 파악하여 이를 활용해 문제를 해결한다.

 

구현

1) 숫자를 1씩 증가시키며 666을 포함하는지 매번 확인하는 방법(브루트 포스)

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <string>

using namespace std;

int main()
{
	int N, Ans = 665;
	cin >> N;

	for (int cnt = 1; cnt <= N; cnt++)
	{
		while (true)
		{
			Ans++;

			if (to_string(Ans).find("666", 0, 3) != string::npos)
				break;
		}
	}

	cout << Ans << "\n";
	return 0;
}

 

 

2) 규칙성을 이용해 보다 빠른 속도로 해결하는 방법 (특수한 경우)

이 방법은 (문제에서 정의한) 종말의 수 중에서 23995 번째 종말의 수인 6660000 보다 앞에 등장하는 종말의 수를 구할 때만 유효하게 사용할 수 있는 방법이므로, 그냥 단순 참고만 하는 것을 추천한다.

 

종말의 수에서 '666' 을 기준으로 왼쪽의 숫자를 $l$, 오른쪽의 숫자를 $r$ 이라고 하면, 1 번째 종말의 수인 666부터 나열했을 때 어떠한 규칙성이 있는 것을 확인할 수 있다.

 

N	1	2	3	4	5	6	7	8	9
종말의 수	666	1666	2666	3666	4666	5666	6660	6661	6662

 

N	10	11	12	13	14	15	16	17	18
종말의 수	6663	6664	6665	6666	6667	6668	6669	7666	8666

 

숫자 $l$ 이 0부터 5까지 1씩 증가함에 따라 오름차순으로 종말의 수가 되지만, 이후 $l$ 이 0이며, $r$ 이 한 자리 숫자인 경우가 총 10번 나타난 다음, 다시 $l = 7, 8 ,9$ 와 같은 순서로 종말의 수가 등장한다.

 

이를 일반화 시켜보면 숫자 $l$ 이 적당하게 증가할 때까지 ($l < 6660$ 인 경우) $l$ 의 오른쪽부터 6을 연속적으로 포함하는 갯수만큼, $r$ 을 작은 수부터 차례대로 채워넣음으로써 종말의 수를 만들 수 있다. 하지만 이 방법은 $l = 6660$ 부터는 성립하지 않는 규칙성임을 반드시 염두에 두어야한다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <string>

using namespace std;

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

	int n = 0;
	int cnt = 0;
	while (true)
	{
		int left = n;
		int sixes = 0;
		int tens = 1;
		while (true)
		{
			if (left % 10 == 6)
			{
				sixes++;
				tens *= 10;
				left /= 10;
			}
			else
				break;
		}

		if (sixes)
		{
			for (int i = 0; i < tens; i++)
			{
				string right = to_string(i);
				while (right.size() < sixes)
					right = "0" + right;

				if (++cnt == N)
				{
					cout << stoi(to_string(left) + "666" + right) << "\n";
					return 0;
				}
			}
		}
		else
		{
			if (++cnt == N)
			{
				cout << stoi(to_string(n) + "666") << "\n";
				return 0;
			}
		}
		n++;
	}
}

 

실행 결과

64 ms: 일반적인 풀이(브루트 포스), 0 ms: 문제의 특성을 이용해 규칙성을 활용한 풀이