1436 - 영화감독 숌

(문제보기)

영화감독 숌 성공분류

 

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

24064

10493

8693

44.749%

문제

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

1. 문제 살펴보기

연속된 숫자 666이 들어간 값을 계속해서 찾는 문제이다.

 

166, 1666, 2666, 3666, ... 

 

여기서 주의할 사항은 N+'666' 만으로는 풀 수 없다.

6336663 와 같이 중간에 666이 들어가 있거나,

6660, 6661, 6662, ... 와 같이 666이 쭉 이어지는 구간이 존재한다.

 

즉, 이 문제를 풀기 위한 단계는 두가지로 나눌 수 있다.

 

1. 연속된 숫자(666)을 찾는다.
2. 1번을 N개 찾을때까지 반복한다.

그렇기 위해서는 다음을 고안해야한다.

• 연속된 숫자(666)를 찾는 방법

 

이번 문제에서는 3칸짜리 작은 큐를 하나 만들어서 진행하였다.

 

666 을 예시로 들어보겠다.

-1

-1

-1

1. 큐를 -1로 초기화 한다.

2. 값을 10으로 모드연산 한 값을 큐에 넣는다. ( 666%6 )

   단, 배열의 2번째, 1번째, 0번째 인덱스 순으로 처음엔 넣는다.

-1

-1

6

3. 이후 값을 10으로 나눠준다. (666/10 = 66)

4. 큐를 확인하여 666이 저장되어 있는지 확인하고, 저장되어있다면 count를 1 증가시킨다.

   그렇지 않다면 다음 단계로 진행한다.

5. 2번으로 돌아가서 반복한다. 값이 0이 된다면 반복을 종료한다.

 

이 과정을 진행하면 다음과 같은 과정이 진행된다.

 

(2번째 반복, 시작값 66)

-1

6

6

큐 확인결과 : 666이 아님

 

(3번째 반복, 시작값 6)

6

6

6

큐 확인 결과 : 666 발견. count 증가

 

위의 방법을 사용한다면 작은 값부터 비교를 진행하기 때문에 문제의 요구조건을 만족할 수 있다.

 

이제 남은 일은 연속된 숫자를 찾는 방법을 고안했으니, N번째 숫자를 찾을 때 까지 반복하는 일만 남았다.

 

이를 위하여 count라는 변수를 만들었고, count가 N과 동일해지면 반복을 중단하면 된다.

 

2. 소스코드

// #1436

#include<stdio.h>

int queue[3] = {-1, -1, -1};

//init Queue
void init(){
        for(int i=0; i<3; i++)
                queue[i] = -1;
}

//insert
void inqueue(int input){
        if(queue[2] == -1)
                queue[2] = input;
        else if(queue[1] == -1)
                queue[1] = input;
        else if(queue[0] == -1)
                queue[0] = input;
        else{
                queue[2] = queue[1];
                queue[1] = queue[0];
                queue[0] = input;
        }
}

//check 666
int check(){
        if(queue[0] == 6 && queue[1] == 6 && queue[2] == 6)
                return 1;
        else
                return 0;
}

int main(void){
        int N;
        int num=0;
        int count = 0;

        scanf("%d", &N);

        while(count != N){
                num++;
                int temp = num;
                init();
                while(temp != 0){
                        inqueue(temp%10);
                        temp = temp/10;

                        //find 666
                        if(check()){
                                count++;
                                break;
                        }
                }
        }

        printf("%d", num);
        return 0;
}

 

큐를 사용하다보니 함수를 몇개 나눠서 코드를 작성했다.

큐에 삽입하는 방법은 쉬엄쉬엄 만들긴 했는데 채점엔 별 이상 없었다.

물론 큐가 저렇게 작으면 그냥 인덱스에 바로 접근해서 비교하는게 훨씬 나을것 같다는 생각도 든다..