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

 

문제 풀이 순서는 간단하다.

1. 몇 번째 영화 시리즈인지 n 값 입력 받기

2. 초기값 설정

3. 종말의 수 구하기

 

 

1번과 2번 과정을 한 번에 수행하면 아래와 같다.

int n;
cin >> n;

int num = 666;
int cnt = 1;

 

cnt 값의 초기값을 1로 설정한 이유는 다음과 같다.

첫 번째 '종말의 숫자'는 666이기 때문에 하나를 이미 찾았다고 가정한다.

 

n번째 종말의 수를 찾을 때까지 while 문을 돌려주자.

while (cnt != n) {
    num++;
    ...
    }
}

 

n의 값을 증가시켜주는 이유는 숫자를 하나씩 키우면서 666이 포함된 수를 찾아야하기 때문이다.

666이라는 수가 포함되어있는지의 여부를 판단하기 위해서는

int → string 의 형변환 작업이 필요하다.

string st = to_string(num);

 

 

666이 포함된 위치를 찾아주기 위해서는 아래와 같이 코드를 작성해야한다.

만약, 찾지 못한다면 string::npos를 반환하게 된다.

if (st.find("666") != string::npos) {
	cnt++;
}

 

 

666이 포함되어 있다면, cnt 값을 하나 증가시켜준다.

 

 

전체 코드

#include <iostream>
#include <string>

//영화감독 숌
using namespace std;

int main(){
    int n;
    cin >> n;

    int num = 666;
    int cnt = 1;

    while(cnt != n){
        num++;
        string st = to_string(num);
        if(st.find("666") != string::npos){
            cnt++;
        }
    }
    cout << num << '\n';
}

 

 

실버5 난이도의 문제였다. 숫자를 하나씩 증가하게 되면 시간복잡도가 높게 나올 줄 알았는데 제출하니까 정답이라고 해서 기분은 좋았다.

아직도 시간복잡도가 헷갈리고 어렵다. 이 문제에서 요구하는 것은 시간복잡도가 아닌 '브루트포스' 알고리즘이었지만, 보통의 문제에서 시간초과로 틀리는 경우가 허다하다보니... 잔뜩 긴장을 하는 것 같다. 알고리즘 문제를 좀 더 열심히 자세하게 공부해야겠다.

 

 

 

 

 

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️