[C/C++] 프로젝트 오일러 #112 Bouncy Numbers(단순반복)

Project Euler 문제 112, “Bouncy Numbers”는 숫자의 특성을 분석하는 문제입니다. 여기서 “Bouncy Number”란 증가하는 숫자도 아니고 감소하는 숫자도 아닌 숫자를 의미합니다. 증가하는 숫자는 각 자릿수가 왼쪽에서 오른쪽으로 갈수록 같거나 커지는 숫자입니다. 예를 들어 123, 455, 789와 같은 숫자는 증가하는 숫자입니다. 반대로 감소하는 숫자는 각 자릿수가 왼쪽에서 오른쪽으로 갈수록 같거나 작아지는 숫자를 말합니다. 예를 들어 321, 876, 954와 같은 숫자는 감소하는 숫자입니다. 그러나 132와 155349 같은 숫자는 증가하거나 감소하는 패턴이 없으므로 Bouncy Number로 분류됩니다.

 

문제는 Bouncy Number의 비율이 특정 퍼센티지(예: 50%, 99%)에 도달하는 가장 작은 숫자를 찾는 것입니다. 이를 해결하기 위해 먼저 특정 숫자가 Bouncy Number인지 판단하는 조건을 구현해야 합니다. 이는 숫자의 각 자릿수를 비교하여 증가와 감소의 패턴이 모두 나타나는지를 확인함으로써 가능합니다. 이후 숫자를 순차적으로 탐색하며 Bouncy Number의 개수를 누적하고, 전체 숫자 중 Bouncy Number가 차지하는 비율을 계산합니다. 이 비율이 목표값에 도달하는 순간 탐색을 종료하고 그 숫자를 출력하면 됩니다.

 

문제의 핵심은 효율적으로 숫자를 탐색하고, Bouncy Number 여부를 빠르게 판별하는 알고리즘을 구현하는 것입니다. 이 과정에서 목표 비율에 근접하는 정확한 계산이 중요하며, 숫자가 커질수록 Bouncy Number의 비율이 증가하는 경향이 있다는 점을 이용할 수 있습니다.

 

bouncy numbers

 

제가 문제를 풀기 위해서 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #112 - Bouncy Numbers
//        - by Aubrey Choi
//        - created at 2015-11-04
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include "isprime.h"

//#define    RATIO    50
//#define    RATIO    90
#define    RATIO    99

bool IsBouncy(int n)
{
    bool isInc = true, isDec = true;
    int last = n%10;
    n /= 10;
    while( n && (isInc || isDec) )
    {
        int c = n%10;
        n/=10;
        if( c > last ) isInc = false;
        if( c < last ) isDec = false;
        last = c;
    }
    return !(isInc || isDec);
}

void solve1()
{
    int bcount = 0;
    int n = 100;

    while( bcount*100 < n*RATIO )
        if( IsBouncy(++n) ) bcount++;

    printf("Ans = %d\n", n);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);
}

 

1. IsBouncy 함수: 숫자가 Bouncy Number인지 판별하는 함수.
• 증가하는 숫자(isInc)와 감소하는 숫자(isDec) 여부를 판별.
• 숫자를 자릿수 단위로 나누며 조건 확인.
• 둘 중 하나라도 유지되면 해당 숫자는 Bouncy Number가 아님.
• 둘 다 아니면 Bouncy Number로 판정.

 

2. solve1 함수: 목표 비율에 도달하는 최소 숫자를 찾는 함수.
• Bouncy Number의 개수를 누적(bcount)하며 숫자를 증가시킴.
• Bouncy Number 비율(bcount / n)이 목표치(RATIO)에 도달하면 종료.
• 결과를 출력.

 

3. main 함수: 실행 시간을 측정하며 문제를 해결.
• clock()을 사용하여 실행 시간을 계산.
• solve1 호출 및 결과 출력.

소스 코드 설명

이 프로그램은 Project Euler 문제 112, Bouncy Numbers를 해결하는 C 코드입니다. 목표는 Bouncy Number의 비율이 특정 퍼센티지(RATIO 값)에 도달하는 최소 숫자를 찾는 것입니다.

 

1. IsBouncy 함수:
• 이 함수는 입력받은 숫자 n을 자릿수별로 비교하여 Bouncy Number 여부를 판별합니다.
• 처음에는 숫자가 증가(isInc = true) 및 감소(isDec = true)하는 조건을 모두 만족한다고 가정합니다.
• 숫자의 마지막 자릿수(last)와 두 번째 자릿수(c)를 비교하여:
• 증가 조건을 위반하면 isInc = false.
• 감소 조건을 위반하면 isDec = false.
• 반복문이 종료될 때 isInc와 isDec가 모두 false라면 Bouncy Number로 판정합니다.

 

2. solve1 함수:
• 이 함수는 Bouncy Number 비율이 RATIO에 도달하는 최소 숫자를 찾습니다.
• 초기 숫자를 100으로 설정(100 이하의 숫자는 Bouncy Number가 아니기 때문).
• 반복문을 통해 숫자를 하나씩 증가시키며 IsBouncy로 판별.
• Bouncy Number라면 bcount를 증가시킵니다.
• Bouncy Number의 비율이 bcount * 100 / n으로 계산되며, 목표 RATIO를 넘으면 반복을 종료합니다.
• 결과를 출력합니다.

 

3. main 함수:
• clock()을 사용하여 프로그램의 실행 시간을 측정합니다.
• solve1 함수를 호출하여 문제를 해결한 뒤 결과와 실행 시간을 출력합니다.

추가 정보
• RATIO 값: 목표 비율을 설정하는 매크로 정의입니다(기본값: 99%).
• 효율성: Bouncy Number 판별 과정에서 숫자를 자릿수 단위로 나누는 방식으로 최소한의 계산으로 조건을 확인합니다.
• 실행 시간 측정: clock()을 이용하여 프로그램의 실행 시간을 초 단위로 표시합니다.