[백준 1436번/C언어] 영화감독 숌 브루트포스로 풀이

백준 1436번 문제를 브루트포스 알고리즘으로 풀어보았습니다. 

백준 1436번 : https://www.acmicpc.net/problem/1436

1436번: 영화감독 숌

 

 

문제 내용은 아래와 같습니다. 예제 입출력은 7개가 준비되어 있으니, 접속하여 확인하기 바랍니다. 여기서는 최소한의 문제 이해를 위한 첫 번째 예제만 두었습니다. 

 

 

 

우선 해당 문제를 해결하기 위해 브루트포스(brute force) 알고리즘을 알아보았습니다. 브루트포스를 직역하면 '무식한 힘'이라는 뜻으로, 그 뜻에 걸맞게 무식하게 하나하나 모든 경우의 수를 체크해 보는 알고리즘을 뜻합니다. 결국 해당 문제는 존재하는 모든 경우의 수를 체크하여 결괏값을 도출해내야 하기 때문에 모든 경우의 수를 반복하는 과정에서 불필요한 과정을 최소화하는 것이 핵심이라고 볼 수 있습니다. 즉, loop 안에서 불필요한 과정을 최대한 삭제하고 꼭 필요한 과정만을 담아, 반복횟수를 최소화하고, 속도를 높여야 하는 것이 주요 과제라고 볼 수 있습니다. 

 

이를 이용하여 코드를 아래와 같이 구성해보았습니다.

코드에 대해 대략적으로 설명하면, 첫 번째 제목인 666부터 하나씩 더하면서 해당 숫자를 문자열로 변환하여 6이 3번 이상 반복되면 N을 하나씩 줄여가면서 N이 0이 될 때의 수를 찾는 방식으로 N번째 제목을 찾습니다. 

#include <stdio.h>
#include <string.h>

// 6의 개수를 세기 위해, integer 형태의 숫자를 char 배열로 바꾸는 함수
void myItoa(int intN, char *charN) {
    int i = 0;
    while (intN != 0) {
        charN[i++] = (intN % 10) + '0';
        intN /= 10;
    }
    charN[i] = '\0';
    // 원래의 itoa함수라면 reverse 과정을 포함해야 하지만, 여기서는 연속된 6의 개수만 정확하게 세면 되기 때문에 해당 과정 생략
}

int main() {
    int N;
    scanf("%d", &N);
    
    long int title = 666; 	// 초깃값으로 666주기 (1~665까지의 불필요한 반복 생략)
    char temp[20];			// str형태의 current title 저장을 위한 문자열
    int count6;				// 6의 개수를 count하기 위한 변수
    
    while (N > 0) {
        myItoa(title, temp);  // 현재의 title값을 문자열로 변환
        count6 = 0;	// count6 값 초기화
        for (int i = 0; i < strlen(temp); i++) {
            if (temp[i] == '6') {
                count6++;
                if (count6 >= 3) {  // 연속된 6이 3개 이상일 경우
                    N--;
                    break;
                }
            }
            else count6 = 0;  // 연속이 끊어졌으므로 처음부터 다시 세어야 함
        }
        title++;
    }
    
    printf("%ld", title-1);  
}

 

 

여기서 myItoa() 함수를 통해, 숫자를 문자열로 구현시켰는데, 초기에는 myItoa() 함수를 작성하지 않고, <stdlib.h> 패키지에 포함된 itoa() 함수를 사용했습니다. 이 코드는 vscode에서 실행시켰을 때는 정상적으로 작동했으나, 막상 백준에 제출하니 아래와 같은 컴파일에러가 발생했습니다. 

 

원인을 구글링해 본 결과, itoa 함수의 경우 non-standard function이기 때문에 어떤 C standard library에서는 존재하지 않을 수도 있다고 합니다. 결국 백준에서 제공하는 standard library에서는 itoa함수가 존재하지 않아 해당 에러가 발생한 것으로 보입니다. 따라서 아래 링크를 참고해 직접 itoa 함수를 구현하고, 이를 myItoa라 명명했습니다. 

https://en.wikibooks.org/wiki/C_Programming/stdlib.h/itoa

C Programming/stdlib.h/itoa - Wikibooks, open books for an open world

 

기본적으로 itoa함수는 아래와 같이 정의되는 함수로, val에 문자열로 변환하기를 바라는 integer를 넣고, buf에 문자열로 변환된 integer가 들어갈 문자열 변수를 넣습니다. 마지막으로 radix에 몇 진수인지를 넣어주면 val이 문자열로 변환되어 buf에 들어가는 식입니다. 

char *itoa(int val, char *buf, int radix);

 

따라서 위 링크에서는 아래와 같이 itoa를 구현하고 있습니다.

 

하지만 제가 정수를 문자열 형태로 변환하는 이유는 단순히 연속된 6의 개수를 세기 위함입니다. 10진수만 사용할 것이고, 6의 개수만 세면 되기 때문에 radix 인자도 필요하지 않고(해당 링크에서는 구현하고 있지 않긴 합니다), 굳이 순서를 reverse하여 진짜 제가 넣은 숫자와 같은 순서로 출력되도록 할 필요도 없습니다. (reverse는 내장 함수가 아니라 직접 구현해야 하기 때문에 넣게 되면 상당히 번거로울뿐더러 저는 반복을 많이 해야 하므로 코드가 돌아가는 속도도 현저히 느려질 수 있습니다.) 따라서 제가 구현한 myItoa는 불필요한 부분을 완전히 제외하고 해당 문제에서 필요한 만큼만 구현해서 아래와 같이 사용했습니다.

void myItoa(int intN, char *charN) {
    int i = 0;
    while (intN != 0) {
        charN[i++] = (intN % 10) + '0';
        intN /= 10;
    }
    charN[i] = '\0';
}

 

 

 

이렇게 문제를 해결한 결과, 백준에서도 잘 성공한 것을 볼 수 있습니다.