[BOJ 백준] 1436 - 영화감독 숌 (C++)

문제 바로가기

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

1436번: 영화감독 숌

---

관련 알고리즘

- 브루트포스

---

정답 및 해설

정수 N을 입력받아 '666'이 포함되어 있는 숫자 중 N번째로 작은 수를 구하는 문제이다.

문제의 제한시간도 2초로 넉넉하게 주어졌고, N의 범위가 1~10000이기 때문에 브루트포스 알고리즘으로 해결하였다.

변수를 하나씩 늘려가면서 '666'이 포함되는지 여부를 체크하면서, 포함된다면 몇 번째인지 찾아 N번째 수가 나올 때까지 반복하여 정답을 찾는다.

---

C++

#include<iostream>
using namespace std;
int main(){
    int N,num=0,i=665,j;
    cin>>N;
    while(num!=N){
        j=++i;
        while(j>=666){
            if(j%1000==666){
                num++;
                break;
            }
            j/=10;
        }
    }
    cout<<i;
}

 

Line	해설
4	int N : N번째로 작은 '666'이 포함된 정수를 구해야 함 int num : 현재 확인한 수가 '666'이 포함된 정수 중 몇 번째인지 나타냄 (0으로 초기화) int i,j : num을 계산하기 위한 임시변수 (i는 665로 초기화)
5~6	정수 N을 입력받고 while 반복문으로 num과 N이 같아질 때 까지 반복한다.
7~15	j=++i; 문으로 i에 1을 더한다음 j에 대입한다. 처음 반복문으로 들어왔을 때 i=665 였기 때문에 j는 i에 1을 더한 666이 된다.
8~14	j>=666 을 만족하는 동안 while 문을 반복한다. if 조건문으로 j%1000==666, 즉 j의 마지막 세 자리수가 666일 경우 num을 1 증가하고 break문으로 while문의 반복을 종료한다. 이때 num변수는 현재 정수 j(=i)가 '666'이 포함되는 숫자 중 작은 순으로 몇번째인지 나타낸다. if 문이 거짓일 경우 j/=10으로 j의 마지막 한 자리수를 제외하고 다시 if문으로 돌아간다. 해당 구문을 통해 j를 한 자리씩 지워가면서 '666'이 포함되는지 확인한다. 정수 j가 j<666 이된다면 '666'이 등장할 수 없기 때문에 while 문을 종료하고 처음의 while 문으로 돌아간다. 그 후, 다시 j=++i; 구문을 통해 i에 1을 증가한 후 위 과정을 반복하여 num과 N이 같아질 때 까지 반복한다.
16	위 반복문에서 num==N일 때 반복문을 종료하여 마지막 i가 '666'이 포함되는 num(=N)번째 정수이다.