[C++] 백준 1436번 영화감독 숌

1. 문제이해

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

1436번: 영화감독 숌

 

영화감독 숌은 종말의 숫자가 들어간 영화제목을 지으려고 한다.

종말의 숫자란 '666'이 들어가는 숫자를 이야기하며, 666,1666,2666... 순서대로 커진다.

이러한 순서대로, 영화의 제목을 정할때,

N번째 영화의 제목에 들어간 수를 출력하면 되는 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

문제를 처음 봤을 때 든 생각은 엥? 너무쉬운데? 라는 생각이었다.

하지만 이는 역시나 착각이었다..  문제를 완전히 다르게 이해했기 때문인데,

이해하고 나서 구현하기는 쉬웠지만, 문제를 이해하기까지의 시간이 오래 걸렸던 문제였다.

처음 문제를 접했을 때의 생각은, 그냥 '666' 앞에 N-1 숫자만 붙여주면 되는거 아닌가? 라는 생각이었다.

666, 1666, 2666, 3666, 4666, 5666, 6666, 7666...처럼 말이다.

하지만 문제에서 이야기 하는 종말의 숫자는 위와 같은 형태가 아니라,

6660, 6661, 6662... 같은 숫자들 또한 포함한다.

'666' 이 적어도 3개이상 들어가는 숫자가 종말의 숫자의 정의이기 때문이다.

 

따라서, 가장 작은 종말의 숫자인 666부터 시작해,

단순히 숫자를 하나씩 증가시켜주며 다른 종말의 숫자를 찾는 알고리즘을 구현하면 되는 문제였다.

숫자를 증가시켜가면서, '666'이라는 문자가 다시 발생하면 그것을 체크하고,

체크한 값이 처음 입력한 N값과 동일한 경우에 이를 출력해주는 식으로 구현하였다.

 

하나 더 추가하자면, 위와 같은 방식의 알고리즘을 '브루트포스 알고리즘 (Brute Force Algorithm)' 이라고 한다.

브루트포스 알고리즘이란, brute(무식한), force(힘) 에서 유추할 수 있듯이,

가능한 모든 경우의 수를 모두 탐색하고, 요구조건에 충족되는 결과를 가져오는 알고리즘이다.

즉, 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.

이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다는 것이다.

 

 

 

3. 소스코드

#include <iostream>
#include <string>

using namespace std;

int main() {

	int title;	// 영화제목 (666부터 시작)
	string stitle;	// 영화제목 문자열로 변환(666 체크위함)
	int check = 0;
	int N;	// N번째 영화

	// 몇번째 영화인지 입력
	cin >> N;

	for (title = 666; ; title++) {	// 가장 작은 종말의 숫자인 666부터 탐색
		stitle = to_string(title);	// string 형으로 바꿔줌

		if (stitle.find("666") != -1) {	// 666을 찾은 경우
			check++;	// check 값을 증감
			if (check == N) {	// check값과 N값이 같아지면, 출력
				cout << title;
				break;
			}
		}
	}
	return 0;
}

2. 문제이해 부분에서 이야기했듯이, 알고리즘의 구현은 비교적 간단했다.

단순히 가장 작은 종말의 숫자인 666부터 시작해서,

값을 1씩 증가시켜 가며 또 다른 종말의 숫자를 차례로 찾아나가는 방식으로 구현했다.

 

int값의 title을 수월한 비교를 위해 string형으로 변환, 변환한 값에서 666이 있으면 체크해주고,

체크 값이 입력한 N값과 같으면 그때의 title 값을 출력해주었다.

 

 

---

오늘째로 실버 5단계 5번째 문제인데, 원래는 10문제 정도 풀고 실버 4단계로 넘어갈 계획이었다.

근데 오늘도 느낀점이, 5단계와 병행하거나 더 하고 넘어가야될 것 같다는 것이다..😥

아직도 실버 5단계 문제들을 보면 모르겠거나 이해가 안되는 문제들이 많다..

2~30문제는 풀고 넘어가야지 좀 성에 찰것같은 느낌이다..😤