백준 알고리즘 1436번: 영화감독 숌 [C++]

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

1436번: 영화감독 숌

1. 코드

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
	int n, cnt = 0;
	cin >> n;

	for (int i = 666; ; i++)
	{
		if (to_string(i).find("666") != string::npos)
			cnt++;
            
		if (n == cnt)
		{
			cout << i;
			break;
		}
	}
	return 0;
}

(실행)

2. 풀이

풀이를 하기 전에 먼저 문제를 살펴보자.

숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.

영화 제목에 666이 연속해서 이어져야하며 작은 순서대로 나열했을 때 N번째 제목을 맞추는 것이다. 그래서 간단하게 666부터 1씩 증가시켜서 N번째가 나올 때까지 반복하는 방법을 생각했다.

	int n, cnt = 0;
	cin >> n;

먼저 사용자에게 입력받을 변수 n과 횟수를 확인하기 위한 cnt를 선언한 뒤 0으로 초기화한다. 그리고 n은 입력을 받는다.

	for (int i = 666; ; i++)
	{

그리고 반복문을 실행하는데 666부터 실행을 한다. 왜냐하면 666 이전의 수에서 6이 세 번 연속 나오지 않기 때문이다. 

		if (to_string(i).find("666") != string::npos)
			cnt++;

그리고 to_string으로 i를 문자열로 변화시켜주고 .find를 이용하여 666이 포함되어있는지 확인한 뒤 그 값이 string::npos가 아니라면 cnt를 1씩 증가시켜주는데 여기서 string::npos는 .find에서 해당하는 값을 문자열에서 찾지못했을 때 나오는 값이다.

		if (n == cnt)
		{
			cout << i;
			break;
		}
	}
	return 0;
}

그리고 cnt값이 n과 같을 때 해당하는 i값을 출력해주고 반복문을 빠져나오고 종료해주면 된다.

3. 느낀 점

처음에는 문제가 이해가 안되어 어떻게 해결하나 고민을 했었는데 문제를 자세히 읽어보니 해답이 있었고, 문자열을 이용하여 생각보다 간단하게 풀 수 있었다.