[백준 / BOJ] - 1436번 영화감독 숌 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [1436] 

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

문제

 

 

영화감독 숌은 작품 시리즈명을 1,2,3 순이 아닌 666, 1666, 2666,... 순으로 한다고 한다.

이 때 N번째 영화의 제목에 들어간 수를 구하는 문제이다.

 

풀이

 

숫자를 문자열로 변경시켜주고, 문자열 내에 '6'이 연속으로 3번 나오는 경우를 모두 찾아 N번째 작품의 제목에 들어간 수를 찾으면 되는 문제이다.

 

단, 많은 사람들이 실수하는 부분이 단순히 루프문 내에 '6'이 3번 연속으로 나오는지만 체크해서는 안된다는것이다.

예를 들어 아래와 같은 루프문이 있다고 했을 때,

 

    while(1)
    {
        target = to_string(i);
        for(int j = 0; j < target.length()-2; j++)
            if(target[j] == '6' && target[j+1] == '6' && target[j+2] == '6')
            {
                series++;
                if(series == N)
                    return i;
            }
        i++;
    }

 

for문 안에 break;문이 없기 때문에 문제가 발생할 수 있다.

예를 들어 숫자 '6666'의 경우, target[0],[1],[2]가 '6'이므로 series++;이 호출되고, 

target[1],[2],[3] 도 모두 '6'이므로 series++;이 또 실행되어 series가 2번 증가하게 된다.

'66666'의 경우엔 3번, '666666' 의 경우엔 4번이 증가할것이다.

 

따라서 루프문 안에 반드시 break 문을 넣어 한번 찾았으면 다음 숫자로 넘어가게끔 해야 한다.

 

코드

 

#include <iostream>
#include <string>
using namespace std;
int Findseries(int N)
{
    int i = 666;
    int series = 0;
    string target;
    while(1)
    {
        target = to_string(i);
        for(int j = 0; j < target.length()-2; j++)
            if(target[j] == '6' && target[j+1] == '6' && target[j+2] == '6')
            {
                series++;
                if(series == N)
                    return i;
                break;
            }
        i++;
    }
}
int main() {
    int N;
    cin >> N;
    cout << Findseries(N);
}

 

평가

 

6666등의 수에서 문제가 발생할 수 있다는 것을 자각하고, for문안에 break 문만 넣어준다면 쉽게 풀 수 있는 문제이다.

정답률은 46.237%로 다소 낮으며, C++이 아닌 다른 언어를 최적화되지 않은 코드로 사용할 경우 시간초과가 발생할 수도 있는 문제이다.