https://www.acmicpc.net/problem/1436
문제
> 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다.
> 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고,
피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.
> 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.
> 종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 이다.
> 따라서, 숌은 첫 번째 영화의 제목은 "세상의 종말 666", 두 번째 영화의 제목은 "세상의 종말 1666"와 같이 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 수) 와 같다.
> 숌이 만든 N번째 영화의 제목에 들어간 수를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.접근
가장 작은 종말의 수 "666"부터 1씩 증가시키며 해당 수에 종말의수가 포함되어있으면 개수를 누적시켜 이 개수와 입력받은 N이 같다면 그때의 수를 출력한다.
문제해결
> 종말의 수를 시작으로 증가시키며 탐색해야 하므로 변수에 담아 시작값으로 잡는다. 종말의 수를 포함한 수가 나오면 누적시킬 cnt 변수도 선언해준다.
> string의 find()함수를 사용하면 쉽게 찾을 수 있다.
find()는 문자열 함수이므로 종말의 수를 문자열로 변화해주고 해당 문자열에서 종말의수 "666"이 있는지 find()한다.
string::npos는 find()했을 때 그 값이 없다면 반환되는 값이다. 즉, 조건문은 666이 존재 한다면에 대한 처리이다.
> 존재한다면 cnt를 누적시킨다. 이는 N번째 종말의 수라는 뜻이다.
이를 입력받은 N과 비교하여 만약 같다면 그 때의 num이 찾고자 하는 종말의 수 이므로 이를 출력한다.
> 아니라면 처음에 초기값으로 준 666에 1씩 더하면서 다시 탐색한다.코드
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
int cnt = 0;
int num = 666;
while (1)
{
string str = to_string(num);
if (str.find("666") != string::npos)
{
cnt++;
if (cnt == N)
{
cout << num << '\n';
break;
}
}
num++;
}
}
후기
처음에 이 문제의 입력에 187이 들어왔을 때 66666이 나오는걸 보고 왜 그런지 모든 경우를 따져봤다. 따져본 후, N번째 종말의 수를 찾기위해 규칙을 수식화 하려는데 예외가 생기고 복잡해지며 끼워맞추기식이 되어갔다.
string처리에 find()라는 함수로 이를 쉽게 해결할 수 있다는걸 새로 알게 되었다. 어떤 문자열을 입력받고 이에 대해 .find("찾으려는 문자열") 하면 있다면 해당 문자열의 위치를 알 수 있고, 없다면 string::npos로 쓰레기값이 반환된다.
이 함수를 사용하니 아주 짧은 코드로 간단하게 해결할 수 있었다. find()를 알기 전 까진 매우 어려운 문제였다.
