[백준] 1436번 영화감독 숌 - C++
문제
666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.
종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그다음으로 큰 수는 1666, 2666, 3666,....이다. 따라서, 숌은 첫 번째 영화의 제목은 "세상의 종말 666", 두 번째 영화의 제목은 "세상의 종말 1666"과 같이 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 수)와 같다.
숌이 만든 N번째 영화의 제목에 들어간 수를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.
입력
첫째 줄에 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.
예제 입력 1
| 2 |
예제 출력 1
| 1666 |
예제 입력 2 복사
| 3 |
예제 출력 2
| 2666 |
예제 입력 3
| 6 |
예제 출력 3
| 5666 |
예제 입력 4
| 187 |
예제 출력 4
| 66666 |
예제 입력 5
| 500 |
예제 출력 5
| 166699 |
풀이과정
처음 문제 접근은 규칙성 찾기로 시도했습니다. 메모장에다가 666이 들어가는 수를 순서대로 쓰니 대충 18번 만에 반복되는 것을 알았습니다. 그래서 주어진 숫자 N을 몫과 나머지로 나누어 몫에 10000을 곱한 값과 나머지-1의 인덱스 값을 더해 출력해 보았습니다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int main(void) {
int num[18] = { 666,1666,2666,3666,4666,5666,6661,6662,6663,6664,6665,6666,6667,6668,6669,7666,8666,9666 };
int N;
int q, r;
cin >> N;
q = N / 18;
r = N % 18;
cout << q * 10000 + num[r - 1];
}
예제 입출력 3까지는 무사히 통과했지만 4부터는 다른 값이 나왔습니다. 자릿수가 늘어날수록 규칙이 변화한다는 것을 간과했기 때문입니다. 그래서 그냥 첫 종말의 수인 666을 시작으로 모든 값을 조사하여 연속으로 666이 나온다면 1씩 카운트하여 N번째 종말의 수를 찾는 방식으로 전수조사 해야겠다고 생각했습니다. 무식한 방법이지만 때론 이런 방법밖에 생각나지 않을 때가 있어서 일단 시도해 보기로 하였습니다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int main(void) {
int N; //타깃 N번째 종말의 수
cin >> N;
int cnt = 0;
int num = 666;
while (1) //첫번째 반복문 : 한번 반복시마다 num값 1 증가
{
if (cnt == N) //N번째 종말의 수를 찾으면 종료
break;
int remain = num; //num값에 변경을 주지 않기 위해 num값 복사
int sixcnt = 0; //6의 개수를 카운트하기 위한 변수
while (1) //두번째 반복문 : 한번 돌때마다 remain의 자릿수 하나씩 검사
{
if (sixcnt > 2) //6의 개수가 3개 이상되면 종료
{
cnt++; //N 카운트 1증가
break;
}
if (remain == 0) //6이 세개 이하여도 remain이 0이되면 종료
break;
if (remain % 10 == 6) //맨 오른쪽 자리가 6이면 카운트
sixcnt++;
else
sixcnt = 0; //아니라면 연속된 6이 아니기 때문에 0으로 초기화
remain = remain / 10; //한번 반복할 때 마다 자릿수 감소
}
num++; //다음 num값 조사를 위한 num++
}
cout << num-1; //마지막에 더한 num++ 제거
}
비록 모든 값을 조사하기 때문에 메모리의 사용과 연산시간은 늘어나지만 모든 예제 입출력이 성공하는 것을 확인했습니다. 제출해 보니 정답이었습니다.
마치며
이번 문제는 문제 이해만 잘한다면 어렵지 않은 문제였던 것 같습니다. 백준 문제를 풀 때 저도 모르게 전수조사나, 무식한 방법은 애써 외면했던 적이 있었는데 그런 것이 때로는 정답이라는 교훈을 얻은 문제인 것 같습니다. 읽어주셔서 감사합니다.