프로그래머스 입문 120871 저주의 숫자 3

2026. 08. 08

문제

이 마을에서는 숫자 3을 저주의 숫자로 여겨, 3의 배수이거나 숫자 3이 포함된 수를 사용하지 않는다.
1 이상 100 이하의 정수 n이 주어질 때, 마을 사람들이 사용하는 숫자 result를 반환하시오.

`n` (10진법)	`result` (마을 전용 숫자)
1	1
2	2
3	4
4	5
5	7
6	8
7	10
8	11
9	14
10	16
15	25
40	76

풀이

n번 세며 결과 보정하기

#include <stdbool.h>

bool is_forbidden_number(int n)
{
    if (n % 3 == 0)
        return true;

    while (n > 0)
    {
        if (n % 10 == 3)
            return true;

        n /= 10;
    }

    return false;
}

int solution(int n)
{
    int result = 0;

    for (int i = 0; i < n; i++)
    {
        result++;

        while (is_forbidden_number(result))
            result++;
    }

    return result;
}

n이 9일 때 14를 반환하는 이유는, 마을의 방식으로 1부터 9번째 숫자까지 세는 과정에서 금지된 숫자 5개를 건너뛰기 때문이다.
일반적인 10진법에서는 1부터 세었을 때 9가 9번째 숫자이다.
하지만 이 마을에서는 특정 숫자를 사용하지 않기 때문에, 1부터 세었을 때 14가 9번째 숫자가 된다.
이제 마을 사람들이 숫자를 세는 규칙에 따라 1부터 9번째 숫자까지 차례대로 세어보자.

1을 만나면 금지된 숫자가 아니므로 첫 번째 숫자가 된다.
2를 만나면 금지된 숫자가 아니므로 두 번째 숫자가 된다.
3을 만나면 3의 배수이므로 건너뛴다.
4를 만나면 금지된 숫자가 아니므로 세 번째 숫자가 된다.
5를 만나면 금지된 숫자가 아니므로 네 번째 숫자가 된다.
6을 만나면 3의 배수이므로 건너뛴다.
7을 만나면 금지된 숫자가 아니므로 다섯 번째 숫자가 된다.
8을 만나면 금지된 숫자가 아니므로 여섯 번째 숫자가 된다.
9를 만나면 3의 배수이므로 건너뛴다.
10을 만나면 금지된 숫자가 아니므로 일곱 번째 숫자가 된다.
11을 만나면 금지된 숫자가 아니므로 여덟 번째 숫자가 된다.
12를 만나면 3의 배수이므로 건너뛴다.
13을 만나면 숫자 3이 포함되어 있으므로 건너뛴다.
14를 만나면 금지된 숫자가 아니므로 9번째 숫자가 된다.

이 방식의 핵심은 숫자를 1씩 증가시키며 순서대로 세어 나가다가, 금지된 숫자를 만나면 금지된 숫자가 아닐 때까지 건너뛰어 유효한 숫자로 보정하는 것이다.

유효한 숫자 n개 세기

#include <stdbool.h>

bool is_forbidden_number(int number)
{
    if (number % 3 == 0)
        return true;

    while (number > 0)
    {
        if (number % 10 == 3)
            return true;

        number /= 10;
    }

    return false;
}

int solution(int n)
{
    int valid_count = 0;
    int current_num = 0;

    while (valid_count < n)
    {
        current_num++;

        if (is_forbidden_number(current_num))
            continue;

        valid_count++;
    }

    return current_num;
}

이전 방식은 숫자를 하나씩 세다가 금지된 숫자를 만나면, 다시 유효한 숫자가 나올 때까지 값을 보정하는 방식이었다.
이 방식도 숫자를 세는 것은 맞지만, 유효한 숫자일 때만 횟수로 인정한다.

n이 9일 때의 의미를 다시 생각해보자.
이는 마을 사람들이 사용하는 숫자 중 9번째 숫자를 찾는다는 뜻이다.
valid_count는 지금까지 발견한 유효한 숫자의 개수를 나타낸다.
따라서 숫자를 하나씩 확인하면서 유효한 숫자를 만났을 때만 valid_count를 증가시킨다.
반대로 금지된 숫자를 만나면 valid_count는 증가시키지 않고 다음 숫자를 확인한다.

반복문이 종료되는 시점은 valid_count와 n이 같아지는 순간이다.
즉, valid_count가 9가 되는 순간 9번째 유효한 숫자를 만났다는 뜻이고, 이 값은 current_num에 담겨 있다.