[C/C++] 백준 1436번 - 영화감독 숌 (브루트 포스)

 

 

<코드>

#include<iostream>
using namespace std;

int N, ans, cnt, temp;

int main()
{
	
	cin >> N;

	ans = 0; // 영화 제목
	cnt = 0; // 현재 몇번쨰 종말의 수인지

	while (cnt != N)
	{
		ans++;
		temp = ans;

		// 수에 6이 적어도 3개이상 들어가는지 판별
		while (temp != 0)
		{
			if (temp % 1000 == 666) // 종말의 숫자라면
			{
				cnt++;
				break;
			}
			else temp /= 10; // 일의 자리수 삭제
		}
	}
	cout << ans;
}

종말의 수 예시

666

1666

2666

3666

4666

5666

6660

6661

6662

6663

....

6669

7666

....

 

i를 1부터 1씩 증가하며 모든수를 탐색하고 종말의 수라면 cnt++을 하여 cnt == N이 되는 순간의 i값을 출력합니다.

 

 

// 수에 연속된 "666"이 있는지 판별
while (temp != 0)
{
	if (temp % 1000 == 666) // 종말의 숫자라면
	{
		cnt++;
		break;
	}
	else temp /= 10; // 일의 자리수 삭제
}

코드에서 위의 부분은 현재 숫자가 종말의 숫자인지 판별하는 부분인데,
종말의 숫자는 6이 연속으로 적어도 3개이상 들어가는 수라고 문제에서 정의하고 있습니다. 

예를들어 temp가 11323566625 이라고 생각해보겠습니다.

 

(1) 11323566625 의 경우 666으로 나눠지지 않으니 10으로 나눠줍니다.

(2) 1132356662 의 경우 666으로 나눠지지 않으니 10으로 나눠줍니다.

(3) 113235666 의 경우 666으로 나눠지므로 종말의 숫자이며, 루프를 탈출합니다

 

다른 예시로 temp가 12345 라고 생각해보겠습니다.

(1) 12345 의 경우 666으로 나눠지지 않으니 10으로 나눠줍니다.

(2) 1234 의 경우 666으로 나눠지지 않으니 10으로 나눠줍니다.

(3) 123 의 경우 666으로 나눠지지 않으니 10으로 나눠줍니다.

(3) 12 의 경우 666으로 나눠지지 않으니 10으로 나눠줍니다.

(3) 1 의 경우 666으로 나눠지지 않으니 10으로 나눠줍니다.

(3) 0 이므로 루프를 탈출합니다.

 

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

1436번: 영화감독 숌