B1436

백준 1436번: 영화감독 숌

1) 문제분석:

N이 주어졌을 때, 6이 적어도 3번 이상 반복되는 N번째 숫자를 구해야한다. 일단 가장 간단하게 생각해서 1부터 구하고 싶은 N번째 숫자가 나올 때까지 자연수 하나하나 조건에 해당하는지 살펴볼 수 있다.

조건은 간단하게 6이 3번 이상 반복되는 것이므로, 우선 %(modulo) 연산을 이용해 각 자릿수를 살펴본다. 이 때, six라는 변수를 사용하여 여태까지 연속된 6이 몇 개 있었는지 저장한다. 따라서 6이 나올 때마다 six의 값을 1 증가시켜주는데, 대신 6이 아닌 digit이 나오면 six를 0으로 초기화 한다. 만약 six의 값이 3이 되면 자릿수 따지는 것을 그만두고(while 루프를 나와서) count의 값을 1 증가시켜준다. count의 값이 N과 같아지면 해당 수의 값을 출력하고 프로그램을 종료하면 된다.

처음에는 한 숫자의 모든 자릿수를 따지고나서야 한 숫자에 대한 루프가 끝나도록 코드를 작성해서 틀린 결과가 나왔다. 예를 들어, 14666이라면, 6이 3번 반복되어도 4에서 six의 값이 0이 되어버리는 불상사가 발생한다.

코드

#include <iostream>

using namespace std;

int main(){
    int N;
    int num;
    int count;

    cin >> N;

    count=0; num=666;
    while(true){
        int temp = num; int six = 0;
        while(temp){
            int digit = temp%10;
            if(digit==6) six++;
            else six = 0;

            if(six==3) break;
            temp /= 10;
        }
        if(six==3) count++;
        if(count==N) break;
        num++;
    }

    cout << num;
}

근데 다른 분들의 풀이를 보다가 내것보다 더 깔끔한 풀이를 보았다(https://www.acmicpc.net/source/16861574). 핵심은 한 숫자의 자릿수를 하나씩 줄여나가면서 %1000 연산의 결과가 666이면 6이 적어도 3번 연속되는 숫자라는 것이다. 다른 풀이들을 보다보면 재밌는게 사람마다 아이디어는 비슷해도 구현이 다르다.

그런데 테스트를 통과했다고해서 전부 완벽한 정답은 아닌 것 같다. 다른 방법으로 정답을 맞춘 풀이를 보아서 코드를 읽어보다가 틀린 부분을 발견했는데, 테스트 케이스(N)의 범위가 10,000까지라서 틀린 부분을 잡아내지 못하는 것 같았다.